Minimum Coins Change Problem

Given a set of coin denominations and a target amount, determine the minimum number of coins required to make up that amount. If the amount cannot be formed using any combination of the coins, output -1.

The problem can be tackled using a dynamic programming approach. Let \(dp[i]\) be the minimum number of coins needed for an amount \(i\). The recurrence relation is given by:

\(dp[i] = \min_{\text{coin}\;\in\;coins} \{dp[i-\text{coin}] + 1\}\)

with the base case \(dp[0]=0\). If \(dp[amount]\) remains infinite, then the answer is -1.

inputFormat

The input is provided via standard input (stdin). The first line contains two space-separated integers (n) and (amount), where (n) is the number of available coin denominations and (amount) is the target amount. The second line contains (n) space-separated integers, representing the coin denominations. Note that (n) may be 0, in which case the second line will be empty.

outputFormat

Output a single integer to standard output (stdout): the minimum number of coins required to make up the target amount. If it's not possible, output -1.## sample

3 11
1 2 5

3