Minimum Coins to Make Amount

Given a list of coin denominations and a target amount, determine the minimum number of coins required to form the given amount. If it is not possible to form the target amount using the provided denominations, output -1.

This problem can be solved using dynamic programming. Define \( dp[i] \) as the minimum number of coins needed to obtain the amount \( i \). The recurrence relation is given by:

\( dp[i] = \min_{\text{coin} \leq i}(dp[i - \text{coin}] + 1) \) with the base condition \( dp[0] = 0 \).

inputFormat

The input is received from standard input (stdin) and consists of three lines:

1. An integer \( n \) representing the number of coin denominations.
2. If \( n > 0 \), a line with \( n \) space-separated integers representing the available coin denominations. If \( n = 0 \), this line will be empty.
3. An integer representing the target amount.

outputFormat

Output a single integer (to stdout): the minimum number of coins required to form the target amount, or -1 if it is not possible.

## sample

3
1 2 5
11

3

</p>