1159. Coin Change in Minimum Steps

Given coin denominations (unlimited supply) and a target amount, each step subtracts one coin's value from the amount. Return the minimum number of steps to reduce the amount to exactly zero, or -1 if impossible. The input is JSON {amount, coins}.

Input: JSON {amount, coins}.

Output: Integer — the minimum steps, or -1.

Examples

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

Input: {"amount":7,"coins":[3,5]}
Output: -1
Explanation: Cannot reach zero.

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

Constraints

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

Asked by