Coin Change

Given coin denominations and a target amount, return the fewest number of coins needed to make that amount. Print -1 if it's impossible.

Example

Input: coins 1 2 5, amount 11 Output: 3 (5 + 5 + 1)

Approach

Bottom-up DP over amounts 0..target: for each amount, try every coin and take the best (1 + dp[amount - coin]) across all coins that fit. This is the canonical "unbounded knapsack" shape — each coin can be reused any number of times, unlike 0/1 knapsack.

Input format

Line 1: coin denominations, space-separated Line 2: target amount

Print the minimum coin count, or -1.