1153. Coin Change I — Minimum Coins

Given coin denominations (unlimited supply) and an amount, return the fewest coins needed to make the amount, or -1 if it cannot be made. The input is JSON {amount, coins}.

Input: JSON {amount, coins}.

Output: Integer — the minimum number of coins, or -1.

Examples

Input: {"amount":11,"coins":[1,2,5]}
Output: 3
Explanation: 5+5+1.

Input: {"amount":3,"coins":[2]}
Output: -1
Explanation: Cannot form 3.

Input: {"amount":0,"coins":[1]}
Output: 0
Explanation: Zero coins.

Constraints

• 0<=amount<=10^4
• 1<=coins<=12

Asked by