Taco's Budget Knapsack

In this problem, you are given a set of dishes where each dish has an associated cost and a value. Vani wants to maximize the total value of dishes she can afford without exceeding her budget. Each dish can be chosen at most once. Formally, for each test case, you are given an integer (N) representing the number of dishes and an integer (M) representing the budget. Following that, there are (N) lines each containing two integers denoting the cost and the value of a dish. Your task is to calculate the maximum total value that can be achieved under these constraints.

inputFormat

The input is read from standard input (stdin) and has the following 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 (M), where (N) is the number of dishes and (M) is the budget.
• Then (N) lines follow, each containing two space-separated integers representing the cost and the value of a dish.

outputFormat

For each test case, output a single line containing one integer — the maximum total value that can be achieved without exceeding the budget. The output is printed to standard output (stdout).## sample

4
3 50
10 60
20 100
30 120
4 7
2 10
3 20
4 30
5 40
1 100000
100000 1000
0 50

220
50
1000
0