Coin Change: Minimizing Coin Count

You are given a set of coin denominations and a target value \( mg \). Your task is to determine the minimum number of coins required to sum exactly to \( mg \), using the available denominations. Each denomination can be used an unlimited number of times.

This problem can be solved by dynamic programming using the recurrence:

\( dp[x] = \min_{c \in \text{denominations}}\{ dp[x-c] + 1 \} \) for \( x \geq c \) with \( dp[0] = 0 \).

If there is no way to form the target value, print -1.

inputFormat

The first line contains two integers: ( n ) (the number of coin denominations) and ( mg ) (the target value). The second line contains ( n ) space-separated integers representing the coin denominations.

outputFormat

Output a single integer: the minimum number of coins required to form ( mg ). If it is impossible to form the target value, output -1.## sample

3 6
1 3 4

2