Coin Change Problem

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

The solution is expected to use a dynamic programming approach. The transition can be expressed by the following recurrence: \[ dp[x] = \min_{coin\; in\; coins} \{dp[x - coin] + 1\} \] with the base condition \(dp[0]=0\).

Example:

Input:
3
1 2 5
11
Output:
3

inputFormat

The input is read from standard input. The first line contains an integer n, representing the number of coin denominations. The second line contains n space-separated integers specifying the coin denominations. The third line contains a single integer which is the target amount.

outputFormat

Output a single integer to standard output that represents the minimum number of coins needed to form the target amount, or -1 if the amount cannot be formed using the given coins.## sample

3
1 2 5
11

3