Nina's Snack Selection

Nina loves her snacks, but her backpack has limited capacity. Given a list of snacks with specific weights and enjoyment values, your task is to determine the maximum total enjoyment value that Nina can carry without exceeding the backpack's weight limit.

This problem is a classic 0/1 Knapsack problem. You are provided with:

• An integer N representing the number of snacks.
• An integer W representing the maximum weight capacity of the backpack.
• N pairs of integers, each pair representing w_i (the weight of the i-th snack) and v_i (the enjoyment value of the i-th snack).

You need to choose a subset of these snacks such that the total weight does not exceed W and the total enjoyment value is maximized.

The dynamic programming recurrence used to solve the problem is given by:

$$ dp[i][w] = \max(dp[i-1][w],\ dp[i-1][w-w_i] + v_i) \quad \text{for } w \geq w_i, $$

with the base condition dp[0][w] = 0 for all w.

This recurrence ensures that for each snack, you decide whether to include it in the backpack or not by comparing the results of both choices.

inputFormat

The input begins with an integer T representing the number of test cases. Each test case is described as follows:

• A single line containing two integers, N and W, where N is the number of snacks available and W is the maximum weight capacity of the backpack.
• Followed by N lines, each containing two integers: w_i (the weight of the i-th snack) and v_i (the enjoyment value of the i-th snack).

outputFormat

For each test case, output a single line containing one integer, which is the maximum enjoyment value that can be achieved without exceeding the weight capacity of the backpack.

## sample

1
4 5
1 1
2 4
3 5
4 7

9

</p>