Minimum Coins Needed

Given an integer (n) representing the number of coin denominations, a list of (n) coin values, and a target amount (T), determine the minimum number of coins required to make exactly the target amount (T) using any number of coins. If it is not possible to form the target amount with the given coins, return -1.

The problem can be formulated as finding (dp[T]) with the recurrence: [ dp[i] = \min_{coin \in coin_values,; coin \le i} (dp[i-coin] + 1) \quad \text{for} \quad i = 1,2,\dots,T, ] with (dp[0]=0) and (dp[i]=\infty) initially for (i>0).

inputFormat

The input consists of three lines:

1. The first line contains an integer (n), the number of available coin denominations.
2. The second line contains (n) space-separated integers representing the coin denominations. If (n = 0), this line will be empty.
3. The third line contains an integer (T), the target amount to achieve.

outputFormat

Output a single integer representing the minimum number of coins required to form the target amount (T). If it is not possible, output -1.## sample

3
1 2 5
11

3