Knapsack Maximum Value

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

The problem can be modeled using dynamic programming. One common recurrence is given by the formula: $$dp[w] = \max(dp[w],\; dp[w - weight] + value)$$ where \(dp[w]\) represents the maximum value attainable with a knapsack limit of w.

Note: Each item can be chosen at most once. There are multiple independent test cases.

inputFormat

The first line contains a single integer T, representing the number of test cases. Each test case begins with a line containing two integers N and W, where N is the number of items and W is the maximum weight capacity of the knapsack. This is followed by N lines, each containing two integers representing the value and weight of the item.

outputFormat

For each test case, output a single line containing the maximum total value that can be achieved under the weight constraint.

## sample

2
3 50
60 10
100 20
120 30
2 10
10 5
20 6

220
20

</p>