0/1 Knapsack Challenge

You are given a knapsack with a capacity \(W\) and \(N\) items, each with a specific weight and value. Your task is to determine the maximum total value that can be achieved by selecting a subset of items such that their total weight does not exceed the capacity \(W\). This is the classic 0/1 Knapsack problem.

The solution can be computed using dynamic programming. The recurrence relation is given by:

[ \text{dp}[i][w] = \max\bigl(\text{dp}[i-1][w],, \text{dp}[i-1][w-w_i] + v_i\bigr) ]

where \(w_i\) and \(v_i\) denote the weight and value of the \(i\)-th item respectively, and \(dp[i][w]\) is the maximum value that can be obtained with the first \(i\) items and knapsack capacity \(w\).

inputFormat

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

T
N1 W1
w1 v1
w2 v2
... (N1 lines)
N2 W2
... (N2 lines)
...
NT WT
... (NT lines)

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 capacity of the knapsack). This is followed by \(N\) lines each containing two integers representing the weight and value of an item.

outputFormat

For each test case, output a single integer — the maximum total value that can be put in the knapsack without exceeding its capacity. The outputs for different test cases should be printed on separate lines to stdout.

## sample

1
3 50
10 60
20 100
30 120

220

</p>