You discover a treasure containing n pieces of jewel stones. You have a sack to collect them but it can hold only contents upto weight capacity.

You are given the weight and value of each of the stones - weighti and valuei.

Find the maximum value of stones that you can carry in the sack.

Example

stones(weight, value): [(1, 3), (2, 4), (3, 5), (4, 7)]
capacity: 5
Max value: 10
Explanation: Choose stones at index 0 and 3.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has the following lines:

• The first line contains two space-separated integers ‘n’ and ‘capacity’.
• The next n lines contains two space-separated integers - weight_i and value_i.

Output Format

For each test case, the output contains a line with one integer denoting the maximum value of stones that you can carry in the sack.

Sample Input

2
4 5
1 3
2 4
3 5
4 7
5 25
2 4
6 14
5 13
9 21
8 18

Expected Output

10
57

Constraints

1 <= T <= 10
1 <= n <= 103
1 <= capacity <= 5*103
1 <= weighti <= 103
1 <= valuei <= 103