Coin Change (Minimum Coins)

You are given n coin denominations and a target amount. You have an unlimited supply of each denomination. Return the minimum number of coins whose values sum exactly to amount.

If no combination of coins sums to amount, return -1.

Input format

Line 1: two integers n and amount. Line 2: n space-separated positive integers, the coin denominations. This line is absent when n = 0.

Denominations may repeat; repeats do not change the answer.

Output format

A single line containing one integer: the minimum number of coins summing to amount, or -1 if it is impossible.

Constraints

• 0 ≤ n ≤ 20
• 0 ≤ amount ≤ 10000
• 1 ≤ denomination value ≤ 10000
• amount = 0 is always achievable with 0 coins.

Example

With coins [1, 2, 5] and amount = 11, the fewest coins is 3 (5 + 5 + 1).