Coin Change

You are given an integer array coins representing coin denominations and an integer amount representing a total amount of money.

Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1.

You may assume you have an infinite supply of each kind of coin.

Examples

Example 1:

Input: coins = [1,5,10], amount = 12

Output: 3

Explanation: 12 = 10 + 1 + 1, which uses 3 coins.

Example 2:

Input: coins = [2], amount = 3

Output: -1

Explanation: The amount 3 cannot be made with only coins of denomination 2.

Example 3:

Input: coins = [1], amount = 0

Output: 0

Explanation: No coins are needed to make amount 0.

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4