Coin Change Problem

You are given a set of coins of different denominations and a total amount of money. Write a program to compute the fewest number of coins needed to make up that amount.

If it is not possible to form the amount with the given coins, output -1.

The problem can be mathematically formulated as finding the minimum number of coins required such that:

\( dp[i] = \min_{\{c \mid c \le i\}} (dp[i-c] + 1) \)

where \( dp[i] \) represents the minimum number of coins needed for the amount \( i \), and the base case is \( dp[0] = 0 \).

Input Example: For instance, with coins [1, 2, 5] and amount 11, the minimum number of coins required is 3.

inputFormat

The input is read from standard input (stdin). The first line contains two integers: (n) and (A), where (n) is the number of coin types and (A) is the target amount. The second line contains (n) space-separated integers, the values of the coins.

outputFormat

Output a single integer on standard output (stdout), which is the minimum number of coins required to form the amount (A). If it is not possible, output -1.## sample

3 11
1 2 5

3