Minimum Number of Coins

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 up the given amount. If it is impossible to make the target amount with the given coins, output -1.

The problem can be solved using dynamic programming. Let \( dp[i] \) be the minimum number of coins needed for amount \( i \). The recurrence relation is:

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

with initial condition \( dp[0] = 0 \). If \( dp[amount] \) is still infinity, then output -1.

inputFormat

The input is provided via standard input (stdin) in the following format:

• The first line contains an integer \( n \) representing the number of coin denominations.
• The second line contains \( n \) space-separated integers representing the coin denominations.
• The third line contains an integer representing the target amount.

outputFormat

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

The output should be written to standard output (stdout).

## sample

3
1 2 5
11

3

</p>