Minimum Number of Coins

You are given n types of coins and a target weight W. Each coin has a positive integer weight. Your task is to determine the minimum number of coins required to achieve exactly the target weight W.

If it is impossible to achieve the target weight with the given coins, output -1.

Hint: Use dynamic programming. Define a DP array dp where \( dp[i] \) represents the minimum number of coins required to get a weight of \( i \). The recurrence is:

[ dp[i] = \min_{w \in \text{weights and } i-w \ge 0} (dp[i-w] + 1) \quad \text{for } i \geq 1 ]

This problem is analogous to the coin change problem.

inputFormat

The first line of input contains two integers n and W, where n (1 ≤ n ≤ 1000) represents the number of coin types, and W (1 ≤ W ≤ 10⁴) is the target weight.

The second line contains n space-separated positive integers, representing the weights of the coins.

outputFormat

Output a single integer: the minimum number of coins required to exactly achieve the target weight W. If it is not possible, print -1.

## sample

3 11
1 2 5

3

</p>