Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Happiness

Limits: 1s, 1.0 GB

They say, “Money can’t buy happiness”. Is it really true? May be money can’t give you the eternal peace but you surely can find happiness using money. You can travel the most beautiful places, buy some brand new cars, Eat the best foods and so on. Only if you have enough money. Right? But none in the world have infinite amount of money. We have a limited amount of money and we try to fulfill our need with it.

Let’s just not be too philosophical here. Rather let’s try to solve a problem. If you have a 100$ in hand, 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 (HP). So if you have two options to spend that 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 T (1<=T<=100), which will denote the number of test cases. Then followed T lines each with a number N (1<=N<=100) and the amount of money M(1<=M<=1000). Following each of the N lines will consists two positive integer numbers, the cost of the choice C(1<=C<=1000) and the HP(1<=HP<=1000) of the choice.

Output

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

Samples

InputOutput
1
3 1000
500 500
200 700
700 400
1200

Author
  • ahmed.shamim's Avatar

    ahmed.shamim

Discussion