0/1 Knapsack Problem

You are given a classic 0/1 Knapsack problem. There are N items, each with a weight and a value. Your goal is to determine the maximum total value that can be obtained by selecting a subset of the items such that the total weight does not exceed a given capacity W.

The problem can be stated in the following way:

Given a knapsack with a maximum weight capacity \(W\) and N items with weights \(w_1, w_2, \dots, w_N\) and corresponding values \(v_1, v_2, \dots, v_N\), find the maximum total value that can be achieved without exceeding the weight capacity. Each item can be taken at most once.

Note: Use dynamic programming to solve this problem efficiently.

inputFormat

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

T
N W
w1 v1
w2 v2
... 
wN vN

Here, T is 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). The following N lines each contain two integers representing the weight and value of an item.

outputFormat

For each test case, output a single integer representing the maximum total value that can be achieved without exceeding the weight capacity. Each output should be printed on a new line to standard output (stdout).

## sample

1
3 50
10 60
20 100
30 120

220

</p>