Minimum Number of Packages

You are given a target weight (w) and a set of package weights. Your task is to determine the minimum number of packages required to exactly reach the target weight (w) using any combination of the given packages (each package weight can be used multiple times). If it is not possible to achieve exactly (w) with these packages, output -1.

This problem can be formulated as a variant of the coin change problem. The state (dp[i]) represents the minimum number of packages needed to achieve a total weight of (i). The recurrence relation is given by: [ dp[i] = \min_{\text{for each package }p \leq i} (dp[i-p] + 1) ] with the base condition (dp[0] = 0).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) denoting the number of test cases. Each test case consists of two lines:

1. The first line contains two integers: the target weight (w) and an integer (n) representing the number of available packages.
2. The second line contains (n) space-separated integers, which are the weights of the packages.

outputFormat

For each test case, output a single line containing the minimum number of packages needed to exactly reach the target weight. If it is impossible, output -1.## sample

5
10 4
1 3 4 5
7 3
2 3 5
20 3
2 3 10
1 1
1
8 4
1 3 4 6

2
2
2
1
2