ICE是一个即将毕业的计算机专业大学生，不巧让他遇上了百年不遇的金融风暴，大学生的平均工资顿时从2000多元降到1500元，这让他非常着急。一次偶然的机会，他听到了两个软件公司老板的谈话，知道新员工进公司的薪水是按员工会的算法的个数和类型来发的，即不同算法加的薪水也不一样。例如：KM---100元，SPFA----200元，假如Ice只会这两种算法，那他的工资就只有300元。于是，为了自己美好的未来，Ice开始发奋学习各种算法。当然算法不同，难易程度也不一样，学习所需的时间也就不一样，而Ice离毕业剩下的时间不多了，所以他必须要在剩余有限的时间内学习尽量多的算法来增加他的工资. 现假设Ice在大学期间是个极度堕落的学生，在他决定发奋前，连最简单的算法也不会。而且一天内只能学一个算法，一旦开始学一个算法就必须要把这个算法学会，学完一个之后才能学另外一个算法。学到一半不加钱。

首先输入一个数T表示数据的个数 接下来输入T组数据 每组数据先输入两个整数 N 、M N表示算法的个数，M表示Ice离毕业剩余的天数 接下来输入N行表示N个不同的算法，每行两个数D、A D表示学这个算法所需要的天数，A表示这个算法所能增加的薪水 （T <= 50, 0<= N <= 100, 0<= M <= 1266, 0 < D <= M, 0 <= A <= 300） 所有输入都为整数

输出一行表示他最多能增加多少工资

ice