Maximum Pack Weight

Given a backpack with a weight capacity \(W\) and a list of items with individual weights, determine the maximum total weight that can be packed without exceeding the capacity. This is a classic 0/1 Knapsack problem where each item can either be taken or not. Use dynamic programming to solve the problem.

Note: You only need to maximize the total weight, not the value. Each test case contains one backpack and a list of items.

inputFormat

The first line of the input contains a single integer \(T\) denoting the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers: \(W\) (the maximum weight capacity of the backpack) and \(n\) (the number of items).
• The second line contains \(n\) space-separated integers representing the weights of the items.

Input is to be read from standard input (stdin).

outputFormat

For each test case, output a single line containing one integer: the maximum weight that can be packed into the backpack without exceeding \(W\). The answer for each test case should be printed on a new line to standard output (stdout).

## sample

1
10 4
2 3 4 5

10

</p>