Maximum Total Value in Boxes

You are given T test cases. In each test case, you have N boxes.

Each box is described by two arrays: one for weights and another for values. Although the weights array is provided, it is not used in the calculation. Your task is to select a subset of these boxes such that the sum of their values does not exceed a given capacity, maxValue, while being as large as possible.

This is essentially a subset-sum problem where you need to compute the maximum sum of selected elements (from the values array) such that their total does not exceed the capacity. Each box can be chosen at most once.

Note: The underlying dynamic programming solution employs a technique that iterates in reverse order over the capacity and updates a dp array. The recurrence relation used is:

\( dp[j] = \max\{ dp[j],\; dp[j - v_i] + v_i \} \) for each item with value \( v_i \) and for every \( j \) from \( maxValue \) down to \( v_i \).

inputFormat

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

T
N
weights[0] weights[1] ... weights[N-1]
values[0] values[1] ... values[N-1]
maxValue
... (repeat the above N-case block for T test cases)

For each test case, the first line contains an integer N (the number of boxes), followed by a line of N integers representing the weights (which are ignored), a line of N integers representing the values, and finally an integer maxValue (the maximum allowed total value).

outputFormat

For each test case, output a single line that contains the maximum total value obtainable without exceeding the given maxValue. The output is written to stdout.

result

## sample

2
5
2 3 1 5 4
3 4 2 8 5
10
4
5 8 3 1
12 10 6 7
13

10
13

</p>