i++ OPC 2012 (v2)

Problem Statement:

You are going to invite chief guests for Techofes. There are n guests. You are given the cost required and the popularity of each chief guest. Among the n guests, you can invite any number of guests. But for inviting a guest, you have to pay his required cost. The expected number of audience is the sum of popularity of all the chosen guests. You only have M amount of money in hand. Find the maximum expected number of audience.

Input:

The first line consists of an integer t, the number of test cases. For each test case { The first line consists of 2 integers n and M – the number of guests and the money in hand respectively. Then n lines follows, each line contains two integers - the cost and popularity of each guest. }

Output:

For each test case find the maximum expected number of audience.

Input Constraints:

1<=t<=10
1<=n<=20
0<=cost,popularity<=1000
0<=M<=20000

Note that some chief guests may have no cost

Example:

Sample Input: (blank lines just for clarity)

3

2 8

1 9

5 7

2 2

2 14

2 12

5 9

9 1

6 4

7 15

3 12

9 5

Sample Output:

16

14

16