Coin Change

You are given a set of coin denominations and a target amount. Your task is to determine the minimum number of coins required to make the exact target amount. If it is not possible to obtain the target using the given coins, output -1.

You can solve this problem using dynamic programming. Let \(dp[i]\) represent the minimum number of coins needed to form the amount \(i\). The recurrence relation is given by:

[ dp[i] = \min_{c \in \text{coins},\ i \geq c} {dp[i-c] + 1} ]

with the base case \(dp[0] = 0\). Compute \(dp[target]\) and if its value remains a large number (i.e. not updated), print -1.

inputFormat

The input is given via standard input and consists of three parts:

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

For example, an input could be:

3
1 2 5
11

outputFormat

The output is a single integer printed to standard output, representing the minimum number of coins needed to form the target amount. If it is not possible to form the target, output -1.

## sample

3
1 2 5
11

3