/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
Atcoder 王国では A_1 円, A_2 円, \ldots, A_N 円の N 種類の硬貨が使用されています。
ここで、1=A_1 < \ldots < A_N であり、全ての 1\leq i \leq N-1 に対し、A_{i+1} は A_i の倍数です。
硬貨のみを使って X 円を支払うとき、支払いに使う硬貨の枚数とお釣りでもらう硬貨の枚数の合計の最小値はいくつですか？
正確には、Y が X 以上の整数を自由に動く時、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
出力
答えを出力せよ。
入力例 1
3 87 1 10 100
出力例 1
5
100 円硬貨 1 枚で支払いを行い、10 円硬貨 1 枚と 1 円硬貨 3 枚をお釣りでもらうと、合計枚数は 5 枚になります。
入力例 2
2 49 1 7
出力例 2
7
7 円硬貨 7 枚で支払いを行うのが最適です。
入力例 3
10 123456789012345678 1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000
出力例 3
233
Score : 500 points
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