硬币

题目描述

给出 $N$ 种硬币面值 $A_1$ 至 $A_N$，其中 $1=A_1 \leq A_2 \leq ... \leq A_{N-1} \leq A_N$ 且对于 $2 \leq i \leq N$，$A_i$ 为 $A_{i-1}$ 的倍数。求最小的花费的硬币数量+找零的硬币的硬币数量使得花费硬币币值和 $\geq X$ 且花费硬币币值和 $-$ 找零硬币币值和 $=X$。

输入格式

第 $1$ 行 $2$ 个整数 $N,X$。

第 $2$ 行 $N$ 个整数 $A_1$ 至 $A_N$。保证 $A_1=1$，$A_i>A_{i-1}$。

输出格式

$1$ 行 $1$ 个整数，表示最小硬币总数。

样例输入

3 87
1 10 100

样例输出

5

数据范围

$1 \leq N \leq 60$。

$1 = A_1 < ... < A_N \leq 1 \times 10^{9}$。

$1 \leq X \leq 1 \times 10^{9}$。

对于 $2 \leq i \leq N$，$A_i$ 是 $A_{i-1}$ 的倍数。