最少支付

题目描述

AtCoder 王国流通着 $N$ 种硬币,面值分别为 $A_1$ 日元、$A_2$ 日元、$\ldots$、$A_N$ 日元。

这里满足 $1 = A_1 \lt \ldots \lt A_N$,并且对于每个 $1 \le i \le N - 1$,$A_{i+1}$ 是 $A_i$ 的倍数。

当只用这些硬币支付价格为 $X$ 日元的商品时,支付所用的硬币数与找零所用的硬币数之和的最小值是多少?

准确地说,当 $Y$ 是不小于 $X$ 的整数时,求「恰好凑出 $Y$ 日元所需的硬币数」与「恰好凑出 $Y - X$ 日元所需的硬币数」之和的最小值。

输入格式

输入按以下格式从标准输入给出。

$N$ $X$
$A_1$ $\ldots$ $A_N$

输出格式

输出答案。

样例

3 87
1 10 100

5

如果支付 1 枚 $100$ 日元硬币,并找回 1 枚 $10$ 日元硬币和 3 枚 $1$ 日元硬币,硬币总数就是 $5$。

2 49
1 7

7

支付 7 枚 $7$ 日元硬币是最优的。

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

233

数据范围

• 输入中的所有值都是整数。
• $1 \le N \le 60$
• $1 = A_1 \lt \ldots \lt A_N \le 10^{18}$
• 对于每个 $1 \le i \le N - 1$,$A_{i+1}$ 是 $A_i$ 的倍数。
• $1 \le X \le 10^{18}$