Coin Change (Fewest Coins)

Medium#dynamic-programming· solved by 0 · time limit 2.0 s

Using unlimited coins of the given values, make exactly $x$ with as few coins as possible. Print -1 if impossible. (Greedy fails for values like 1, 3, 4 and $x = 6$ .)

Input

$n$ , then the $n$ coin values, then $x$ .

Output

The minimum number of coins or -1.

Constraints

$1 \le n \le 100$ , $1 \le$ coin $\le 10^4$ , $0 \le x \le 10^4$

Sample 1

Input

3
1 3 4
6

Output

Sample 2

Input

1
2
3

Output

-1