Contest Duration: - (local time) (100 minutes) Back to Home
E - Minimal payments /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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 の倍数です。

### 制約

• 入力に含まれる値は全て整数である
• 1 \leq N \leq 60
• 1=A_1 < \ldots <A_N \leq 10^{18}
• 全ての 1\leq i \leq N-1A_{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


### 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