Fewest Coins

Difficulty: 1500 3000 ms 128 MB

dp

Coins of the given denominations are available in unlimited supply. Print the minimum number of coins summing exactly to T, or −1 if impossible.

Input: the first line has N and T; the second line has the N denominations.

Output: the minimum coin count, or −1.

Constraints:

• 1 ≤ N ≤ 12
• 0 ≤ T ≤ 10⁴
• 1 ≤ c_i ≤ 100

Sample Tests

3 6
1 3 4

2

1 3
2

-1

Read the Editorial