Minimizing Coins

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ distinct positive coin values, each usable any number of times, form exactly sum $x$ with the minimum number of coins; print -1 if impossible.

Input

Line 1 contains $n,x$. Line 2 contains $n$ distinct values $c_1,\ldots,c_n$.

Output

Print the minimum number of coins, or -1 if $x$ cannot be formed.

Subtasks

• Subtask 1 — 20 points: 1 <= n <= 10; 1 <= x <= 30.
• Subtask 2 — 30 points: 1 <= n <= 50; 1 <= x <= 10000.
• Subtask 3 — 50 points: 1 <= n <= 100; 1 <= x <= 1000000; 1 <= c_i <= 1000000; c_i distinct.

Examples

Input

3 11
1 5 7

Output

3

Explanation

With coins $1,5,7$, sum 11 is formed as $5+5+1$ using 3 coins, which is optimal.