Coins

Problem Description

You are given $N$ coin denominations $A_1$ through $A_N$, where $1 = A_1 \le A_2 \le \dots \le A_{N-1} \le A_N$ and for $2 \le i \le N$, $A_i$ is a multiple of $A_{i-1}$. Find the minimum of (number of coins spent) + (number of coins given as change) such that the sum of the spent coins is $\ge X$ and (sum of spent coins) $-$ (sum of change coins) $= X$.

Input Format

The first line contains two integers $N, X$.

The second line contains $N$ integers $A_1$ through $A_N$. It is guaranteed that $A_1 = 1$ and $A_i > A_{i-1}$.

Output Format

One line with one integer — the minimum total number of coins.

Sample Input

3 87
1 10 100

Sample Output

5

Constraints

• $1 \le N \le 60$.
• $1 = A_1 < \dots < A_N \le 1 \times 10^9$.
• $1 \le X \le 1 \times 10^9$.
• For $2 \le i \le N$, $A_i$ is a multiple of $A_{i-1}$.