102314: [AtCoder]ABC231 E - Minimal payments

Problem Statement

There are $N$ kinds of coins used in the Kingdom of Atcoder: $A_1$-yen, $A_2$-yen, $\ldots$, $A_N$-yen coins.
Here, $1=A_1 < \ldots < A_N$ holds, and $A_{i+1}$ is a multiple of $A_i$ for every $1\leq i \leq N-1$.

When paying for a product worth $X$ yen using just these coins, what is the minimum total number of coins used in payment and returned as change?

Accurately, when $Y$ is an integer at least $X$, find the minimum sum of the number of coins needed to represent exactly $Y$ yen and the number of coins needed to represent exactly $Y-X$ yen.

Constraints

• All values in input are integers.
• $1 \leq N \leq 60$
• $1=A_1 < \ldots <A_N \leq 10^{18}$
• $A_{i+1}$ is a multiple of $A_i$ for every $1\leq i \leq N-1$.
• $1\leq X \leq 10^{18}$

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 87
1 10 100

Sample Output 1

5

If we pay with one $100$-yen coin and receive one $10$-yen coin and three $1$-yen coins as the change, the total number of coins will be $5$.

Sample Input 2

2 49
1 7

Sample Output 2

7

It is optimal to pay with seven $7$-yen coins.

Sample Input 3

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

Sample Output 3

233

问题描述

在Atcoder王国中，有N种硬币：A₁日元硬币，A₂日元硬币，...，A_N日元硬币。

这里，1=A₁ < ... < A_N成立，并且对于每一个1≤i≤N-1，A_i+1是A_i的倍数。

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

准确地说，当Y是至少为X的整数时，找出表示Y日元所需的硬币数量和表示Y-X日元所需的硬币数量的最小和。

约束条件

• 输入中的所有值都是整数。
• 1≤N≤60
• 1=A₁ < ... < A_N≤10¹⁸
• 对于每一个1≤i≤N-1，A_i+1是A_i的倍数。
• 1≤X≤10¹⁸

输入

输入将以标准输入的以下格式给出：

$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