TECHOFES - INVITATION FOR TECHOFES

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


Added by:cegprakash
Date:2012-10-14
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-05-30 20:53:20 Shubham
easy simple [spoiler removed].....silly mistake of not seeing that M nd Cost of guest can be zero....
so keep that in mind ....:)

Last edit: 2015-08-10 21:03:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.