当前没有测试数据。

E - 最小支付问题

分数：500 分

问题描述

在 Atcoder 王国有 $N$ 种硬币：$A_1$ 元硬币，$A_2$ 元硬币，$\ldots$，$A_N$ 元硬币。
这里，满足 $1=A_1 < \ldots < A_N$，并且对于任意 $1\leq i \leq N-1$，$A_{i+1}$ 是 $A_i$ 的整数倍。

当用这些硬币支付价值为 $X$ 元的商品时，作为找零的最小总硬币数是多少？

更确切地说，对于至少等于 $X$ 的整数 $Y$，找出表示 $Y$ 元所需的最小硬币数和表示 $Y-X$ 元所需的最小硬币数之和。

约束

• 输入中的所有值都是整数。
• $1 \leq N \leq 60$
• $1=A_1 < \ldots <A_N \leq 10^{18}$
• 对于任意 $1\leq i \leq N-1$，$A_{i+1}$ 是 $A_i$ 的整数倍。
• $1\leq X \leq 10^{18}$

输入

输入以以下格式从标准输入中给出：

$N$ $X$

$A_1$ $\ldots$ $A_N$

输出

输出答案。

3 87
1 10 100

5

如果我们用一枚 100 元硬币支付，并且找回一枚 10 元硬币和三枚 1 元硬币作为找零，总共使用 5 枚硬币。

2 49
1 7

7

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

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

233