Minimum Coin Change Problem

You are given a set of coin denominations and a target amount. Your task is to determine the minimum number of coins required to make exactly the target amount. If it is not possible to achieve the target amount with the given denominations, output -1.

You can formalize the problem using dynamic programming. Let \(dp[i]\) be the minimum number of coins needed to form the amount \(i\). Then the recurrence is:

\(dp[i] = \min_{\text{coin} \leq i} (dp[i-\text{coin}] + 1)\)

with the base case \(dp[0] = 0\). If no combination of coins can sum up to the target, \(dp[target]\) remains infinite and you should output -1.

inputFormat

The input is read from stdin and consists of three lines:

1. The first line contains an integer \(n\) representing the number of available coin denominations.
2. The second line contains \(n\) space-separated integers, each representing a coin's denomination. If \(n = 0\), this line will be empty.
3. The third line contains an integer representing the target amount in cents.

outputFormat

Output a single integer to stdout which is the minimum number of coins required to make the target amount. If it is not possible to form the target amount, output -1.

3
1 2 5
11

3