#P1726. 喜欢玩warcraft的ltl

喜欢玩warcraft的ltl

ltl 非常喜欢玩warcraft,因为warcraft十分讲究团队整体实力,而他自己现在也为升级而不拖累团队而努力。

他现在有很多个地点来选择去刷怪升级,但是在每一个地点他都要买上充足的补给和合适的道具,以免在刷怪的时候被怪物反杀了,每一个地点的怪物打完了就没有了(还居然不掉金钱跟装备),而且他只要选定了地点就一定会刷完该地点全部的怪物,同时获得对应的经验值。现在ltl 能给出每一个地点用来买补给和道具的钱和打完全部怪物所能获得的经验,但是他所拥有的钱是一定的。所以他想知道怎么选择地点使得他获得的经验最高。

Input

第一行一个整数T,表示测试数据的组数 0<T<=10
第二行两个整数N,M,0<N<=100,0<M<=1000000表示ltl拥有N个不同地点的选择和M的金钱总数
接下来N行每行两个整数ci,vi,(0<ci<=1000000,0<vi<=2000)表示ltl刷完第i个地点所需要购买补给和道具的总钱数和能获取的总经验值

Output

一行一个整数,表示ltl能够获取的最大的经验值

Sample Input

2
3 10
7 7
2 3
3 5
2 5
3 5
2 1

Sample Output

</p>
Max experience: 12
Max experience: 6

HINT

Source