Coin Change (Minimum Coins)

Problem

Given coin denominations and an amount, return the fewest coins needed, or -1 if impossible.

Input

Line 1: n and amount. Line 2: n coin denominations.

Output

Min coins or -1.

Constraints

1 ≤ n ≤ 12, 1 ≤ amount ≤ 10^4, 1 ≤ coin ≤ 10^4

Sample input

3 11
1 2 5

Sample output

Explanation

11 = 5 + 5 + 1 → 3 coins.

dpgreedy-failunbounded-knapsack@Amazon@Goldman Sachs@Uber

Visible test cases

in: 3 11
1 2 5

out: 3

in: 1 3
2

out: -1

Your solution — run it, use AI if stuck

java