0/1 Knapsack Problem with Safety Deposit Artifacts

You are given T test cases. In each test case, you are provided with a safety deposit box of capacity \(W\) and \(N\) artifacts. Each artifact is characterized by its size and its value. Your task is to determine the maximum total value of artifacts that can be secured in the deposit box without exceeding its capacity.

This is a classic 0/1 knapsack problem where each artifact can either be taken or left. The decision must ensure that the total size of the selected artifacts does not exceed \(W\), while maximizing the total value.

Input Format: The first line contains an integer \(T\), the number of test cases. For each test case, the first line contains two integers \(N\) and \(W\) denoting the number of artifacts and the maximum capacity, respectively. Each of the next \(N\) lines contains two integers representing the size and the value of an artifact.

Output Format: For each test case, output a single line containing the maximum value that can be obtained.

inputFormat

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

T
N1 W1
size1 value1
size2 value2
... (N1 lines)
N2 W2
size1 value1
size2 value2
... (N2 lines)
... for T test cases

Where:

• T is the number of test cases.
• For each test case, N is the number of artifacts and W is the capacity of the deposit box.
• Each of the following N lines provides the size and value of an artifact.

outputFormat

The output is written to stdout. For each test case, print the maximum total value that can be secured in the safety deposit box. Each answer should be on a separate line.

## sample

1
4 10
4 40
3 50
2 60
5 30

150

</p>