Minimum Number of Coins

You are given a set of coin denominations and a target amount. Your task is to determine the minimum number of coins needed to make up that amount. Each coin denomination is available in infinite quantity. If the target amount cannot be formed using the given coins, output -1.

The problem can be formulated as follows: Let \(dp[i]\) be the minimum number of coins required to achieve the amount \(i\). We have the recurrence:

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

with \(dp[0]=0\). If \(dp[amount]\) remains infinity, then it is impossible to form that amount.

inputFormat

The input is given from the standard input and has the following format:

• The first line contains two integers \(n\) and \(amount\), where \(n\) is the number of coin denominations and \(amount\) is the target amount.
• The second line contains \(n\) space-separated integers representing the coin denominations.

outputFormat

Output a single integer representing the minimum number of coins required to make up the given amount, or -1 if it is impossible.

4 3
1 2 5 11

2