Limits 1s, 1.0 GB

If you have a Tk 100 in your wallet, what would you do? You might have couple of ways to spend that money. But if you are wise you would spend it in such a way that makes you the most happy. For the sake of this problem we will calculate happiness with a imaginary unit called Happy Point (HPHP). So if you have two options to spend that Tk 100, one of which has 200 HP and another has 500 HP, you would certainly spend it for the latter one. Right?

Now, in this problem you will be given a certain amount of money and couple of choices along with their costs and the Happy Points, you need to decide what is the maximum HP you can get by spending that money.

Input

First line will be a number TT (1T1001 ≤ T ≤ 100), which will denote the number of test cases. Then followed TT lines each with a number NN (1N1001 ≤ N ≤ 100) and the amount of money MM (1M10001 ≤ M ≤ 1000). Following each of the N lines will consists two positive integer numbers, the cost of the choice CC (1C10001 ≤ C ≤ 1000) and the HPHP (1HP10001 ≤ HP ≤ 1000) of the choice.

Output

For each test cases, output the maximum HPHP you can get by spending that money.

Sample

InputOutput
1
3 1000
500 500
200 700
700 400
1200

Submit

Login to submit.

Contributors

Statistics

67% Solution Ratio
SuperstormEarliest, Sep '17
riyad000Fastest, 0.0s
minhazmirazLightest, 131 kB
mdshadeshShortest, 391B
Toph uses cookies. By continuing you agree to our Cookie Policy.