Coins 0

Interview

Time limit1sMemory limit256 MB

Summary

Pay exactly K with the fewest coins from denominations where each divides the next.

Level: Easy3 of 10
Topics: Greedy
Solved: No attempts yet

Problem

You have unlimited coins of $N$ denominations. Denominations are sorted ascending, $A_1 = 1$ , and each $A_i$ is a multiple of $A_{i-1}$ . Find the minimum number of coins whose total value is exactly $K$ .

Input

Line 1: $N$ and $K$ ( $1 \leq N \leq 10$ , $1 \leq K \leq 100000000$ ). Next $N$ lines: coin values $A_i$ in ascending order ( $1 \leq A_i \leq 1000000$ ).

Output

Print the minimum coin count.

Examples2

Example 1

Input

Expected output

Example 2

Input

Expected output