Minimum Coin Change

You are given a list of coin denominations and a target amount. Your task is to determine the minimum number of coins required to make the exact amount. If it is not possible to achieve the target using any combination of the coins, print -1.

The problem can be formally described using dynamic programming. Let \(dp[i]\) denote the minimum number of coins needed to form the amount \(i\). The recurrence relation is given by:

[ dp[i] = \min_{\text{for each coin }c \le i} { dp[i-c] + 1 } ]

with the base case \(dp[0] = 0\). If \(dp[amount]\) remains greater than \(amount\) after computing, that means it is not possible to form the amount, and the output should be \(-1\).

inputFormat

The input consists of two lines:

• The first line contains the coin denominations separated by spaces.
• The second line contains a single integer representing the target amount.

outputFormat

Output a single integer which is the minimum number of coins required to form the target amount. If the amount cannot be formed, output \(-1\).

1 2 5
11

3