Fewest Coins

You have as many coins as you like of each value in coins. Write fewest_coins(coins, amount) that returns the smallest number of coins whose values add up to exactly amount, or -1 if no mix of coins makes that amount.

Examples

fewest_coins([1, 3, 4], 6)    # returns 2
fewest_coins([1, 5, 12], 15)  # returns 3
fewest_coins([2, 5], 3)       # returns -1
fewest_coins([7], 0)          # returns 0

For 15, taking the biggest coin first gives 12 + 1 + 1 + 1 (four coins), but 5 + 5 + 5 needs only three.

Constraints

• 1 <= len(coins) <= 12, and the values are all different
• 1 <= coins[i] <= 10000
• 0 <= amount <= 10000