Minimum Coins for Exact Sum

You are given an integer n representing the number of coin types, an array of n positive integers representing the coin values, and an integer m which is the target sum. Your task is to determine the minimum number of coins required to obtain exactly the sum \(m\). If it is impossible to form \(m\) with the given coins, output -1.

The problem can be formulated using the recurrence:

[ dp[i] = \min_{\text{coin} \in \text{coins}} \bigl( dp[i - \text{coin}] + 1 \bigr) \quad\text{for } i \geq \text{coin}, ]

with \(dp[0] = 0\) and \(dp[i] = \infty\) for all other \(i\) initially, where \(i\) ranges from 1 to \(m\).

Example: If \(n = 3\), coins = [1, 2, 5] and \(m = 11\), then the minimum number of coins needed is 3 (e.g., 5 + 5 + 1).

inputFormat

The input is given via stdin and consists of three lines:

• The first line contains an integer n (the number of coin types).
• The second line contains n space-separated integers representing the coin values.
• The third line contains the target sum m.

outputFormat

Output a single integer via stdout, representing the minimum number of coins required to obtain the exact sum \(m\), or -1 if it is not possible.

## sample

3
1 2 5
11

3

</p>