Minimum Number of Coins

You are given several test cases. In each test case, you are provided with an integer M and K coin denominations. Your task is to compute the minimum number of coins required to sum exactly to M using the given coin denominations. If it is not possible to obtain the exact amount M using any combination of the coins, output -1.

The problem can be formulated using dynamic programming. Let \(dp[x]\) denote the minimum number of coins required to obtain the sum \(x\). The recurrence is given by:

[ \text{dp}[x] = \min_{coin \in denominations \text{ and } x \geq coin} {\text{dp}[x - coin] + 1} ]

with the base case \(dp[0]=0\). If \(dp[M]\) remains \(\infty\) (or a very large number), then the answer is -1.

inputFormat

The first line of input contains an integer T indicating the number of test cases.

Each test case consists of two lines:

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

You should process each test case independently.

outputFormat

For each test case, output the minimum number of coins required to form M using the given coin denominations. If it is impossible to form M, output -1. Each result should be printed on a new line.

## sample

2
11 3
1 2 5
30 4
2 3 7 10

3
3

</p>