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 (). 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.
First line will be a number (), which will denote the number of test cases. Then followed lines each with a number () and the amount of money (). Following each of the N lines will consists two positive integer numbers, the cost of the choice () and the () of the choice.
For each test cases, output the maximum you can get by spending that money.
Input | Output |
---|---|
1 3 1000 500 500 200 700 700 400 | 1200 |