Minimum Coins Problem

You are given a set of coin denominations and a target amount of money m. Your task is to determine the minimum number of coins required to sum exactly to m using the available coin denominations. If it is not possible to form the amount m using any combination of the coins, output -1.

The problem can be formulated as follows:

Given an integer n representing the number of coin denominations, a list of n distinct coin values, and an integer m representing the target amount, compute the minimum number of coins required to form m.

The following recurrence relation defines the solution using dynamic programming:

\[ \text{dp}[0] = 0, \quad \text{dp}[i] = \min_{\text{coin} \le i}\{\text{dp}[i-\text{coin}] + 1\}, \quad 1 \le i \le m \]

If no combination can form the target amount, output \(-1\).

inputFormat

The input is read from standard input and consists of three lines:

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

outputFormat

Output a single line to standard output containing one integer: the minimum number of coins required to form the target amount m. If it is not possible, output -1.

## sample

3
1 3 4
6

2

</p>