Minimum Coins for Change

You are given an integer n representing the number of coin denominations, an integer m representing the total amount of money, and a list of n coin denominations. Your task is to compute the minimum number of coins required to form the amount m.

If it is impossible to form the amount m using any combination of the coins, output -1.

The problem can be formally described as follows:

Find the minimum number of coins needed to produce the amount $$m$$ using the given coins. If no combination of coins can produce $$m$$, output $$-1$$.

For example:

• Input: n = 3, m = 11, coins = [1, 2, 5] → Output: 3 (because 5+5+1=11)
• Input: n = 2, m = 3, coins = [2, 5] → Output: -1 (since no combination can sum to 3)

This problem is a classic application of dynamic programming.

inputFormat

The first line of input contains two integers n and m separated by a space, where n is the number of coin types and m is the total amount of money.

The second line contains n space-separated integers representing the coin denominations.

Example:

3 11
1 2 5

outputFormat

Output a single integer: the minimum number of coins needed to form the amount m, or -1 if it is not possible.

Example:

3

## sample

3 11
1 2 5

3

</p>