Vending Machine: Minimum Coins Problem

You are given a series of test cases where each case describes a vending machine scenario. In each test case, you are provided with a list of coin denominations and a target price. Your task is to determine the minimum number of coins needed to exactly achieve the target price. If it is not possible to achieve the price using the given denominations, output -1.

The problem can be solved using dynamic programming. Define a dp array where \(dp[i]\) represents the minimum number of coins required to obtain the value \(i\). The state transition is given by:

$$\text{dp}[i] = \min_{\text{coin}\,\in\,\text{denominations}} \{dp[i - coin] + 1\} \quad \text{for } i \geq coin $$

Initialize \(dp[0]=0\) and set all other entries to a large value (infinity) to simulate an unreachable state. For each coin, update the dp array accordingly. The answer for any test case is \(dp[price]\) if it is not infinity, otherwise output -1.

inputFormat

The input is read from stdin and has the following structure:

1. An integer T representing the number of test cases.
2. For each test case:
   1. An integer M indicating the number of coin denominations.
   2. M space-separated integers representing the available coin denominations.
   3. An integer representing the target price.

outputFormat

For each test case, output a single line to stdout containing the minimum number of coins needed to achieve the target price. If it is not possible, output -1.

## sample

3
4 1 2 5 10 6
3 3 6 9 4
5 1 6 9 12 15 16

2
-1
2

</p>