Coin Change Problem

Given a list of coin denominations and a target amount, your task is to determine the minimum number of coins required to make up that amount. If it is impossible to form the amount using the given coins, output -1.

This problem can be solved using dynamic programming. Define a dp array such that $$dp[i] = \min_{\text{coin}\in \text{coins}}\{dp[i-\text{coin}]+1\}$$ with the base case $$dp[0] = 0$$. The answer is then found in $$dp[\text{amount}]$$ if it is not infinity.

For example, if coins = [1,2,5] and amount = 11, the minimum coins required is 3.

inputFormat

The input consists of three lines:

1. The first line contains an integer n, representing the number of coin denominations.
2. The second line contains n space-separated integers representing the coin denominations.
3. The third line contains a single integer representing the target amount.

outputFormat

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

3
1 2 5
11

3