Minimum Number of Coins

You are given a collection of coin denominations and a target amount. Your task is to determine the minimum number of coins needed to make up the target amount, given that you can use each coin an unlimited number of times.

If it is not possible to achieve the target amount with any combination of the given coins, output -1.

This problem can be efficiently solved using dynamic programming. The state dp[i] represents the minimum number of coins required to achieve the amount i. The recurrence relation is given by:

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

with the base case \( dp[0] = 0 \). If \( dp[target] \) remains unchanged (e.g., set to a value larger than target) then the target is not possible, and you should output -1.

inputFormat

The input is given via standard input (stdin) with the following format:

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

outputFormat

Output a single integer to the standard output (stdout) which is the minimum number of coins needed to form the target amount. If it is not possible to form the target amount, output -1.

3 11
1 2 5

3