题目描述

给你一个下标从 $0$ 开始的整数数组 $coins$，表示可用的硬币的面值，以及一个整数 $target$ 。

如果存在某个 $coins$ 的子序列总和为 $x$，那么整数 $x$ 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 $[1, target]$ 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。

输入格式

第一行输入 2 个整数 $n, target$, 表示 coins 数组的大小和可取的金额的最大值。

接下一行来 $n$ 个正整数，表示可用的硬币面值。

输出格式

输出一个数，表示需要添加的最少的硬币个数

3 19
1 4 10

2

6 19
1 4 10 5 7 19

1

3 20
1 1 1

3

提示

【样例解释 1】

• 需要添加面值为 $2$ 和 $8$ 的硬币各一枚，得到硬币数组 $[1,2,4,8,10]$ 。
• 可以证明从 $1$ 到 $19$ 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 $2$ 。

【样例解释 2】

• 只需要添加一枚面值为 $2$ 的硬币，得到硬币数组 $[1,2,4,5,7,10,19]$ 。
• 可以证明从 $1$ 到 $19$ 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 $1$

【样例解释 3】

• 需要添加面值为 $4$ 、$8$ 和 $16$ 的硬币各一枚，得到硬币数组 $[1,1,1,4,8,16]$ 。
• 可以证明从 $1$ 到 $20$ 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 $3$ 。

数据规模与限制

• $1 \le n \le 10^5, 1 \le target \le 10^5$
• $1 \le coins[i] \le target$
• 1s, 1024KiB for each test case.

来源