← 返回题目列表

AtCoder · abc231_e

H. 最低付款

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N Atcoder王国使用的硬币种类: A_1-日元, A_2-日元, \ldots, A_N- 日元硬币。
在这里, 1=A_1 < \ldots < A_N 成立,并且 A_{i+1} 是的倍数 A_i 对于每个 1\leq i \leq N-1.

为值得的产品付款时 X 仅使用这些硬币的日元,支付时使用并找零退回的硬币总数最少是多少?

准确地说,当 Y 至少是一个整数 X,求准确表示所需硬币数量的最小总和 Y 日元和硬币数量需要准确表示 Y-X 日元。

约束

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

输入

输入由标准输入按以下格式给出:

N X
A_1 \ldots A_N

输出

打印答案。


示例输入 1

3 87
1 10 100

示例输出 1

5

如果我们用一个支付 100-日元硬币并收到一枚 10-日元硬币和三 1-日元硬币随着变化,硬币总数将是 5.


示例输入 2

2 49
1 7

示例输出 2

7

最佳支付方式为七 7- 日元硬币。


示例输入 3

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

示例输出 3

233