Taco Knapsack Problem

You are given a classic 0/1 knapsack problem with a twist. In each test case, you are provided with a set of items where each item has a value and a weight. Your goal is to determine the maximum total value you can accumulate without exceeding the given weight limit.

For each test case, the input starts with two integers \(N\) and \(W\) where \(N\) is the number of items and \(W\) is the maximum allowed weight. This is followed by \(N\) lines each containing two integers \(V\) and \(w\), representing the value and the weight of each item respectively.

Your solution must compute the answer for each test case and output the results; one result per test case. Use dynamic programming to efficiently solve the problem. The state transition for the knapsack is given by:

\[ dp[w] = \max\{dp[w], dp[w - w_i] + V_i\} \]

where \(w_i\) and \(V_i\) are the weight and value of the \(i^{th}\) item, and the iteration is performed in reverse order to avoid counting an item more than once.

inputFormat

The first line of the input contains an integer \(T\), the number of test cases. For each test case, the first line contains two integers \(N\) (the number of items) and \(W\) (the maximum weight capacity). This is followed by \(N\) lines, each containing two integers \(V\) and \(w\), representing the value and weight of an item.

Example:

1
3 50
60 10
100 20
120 30

outputFormat

For each test case, output a single line containing the maximum total value that can be carried without exceeding the weight capacity.

Example:

220

## sample

1
3 50
60 10
100 20
120 30

220

</p>