X的学习计划

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

X追上学妹后,日子过得美滋滋啊。每天和女朋友吃吃饭,逛逛街,时间过得很快啊。快要考试了,可是X什么都不会呀,而且时间不多了,X只能尽量学多一点吧。

Xn科课程都需要学,每一科都有一个学习时间t,和收获s。对于一科可以不学满时间tX想要在有限的时间内有最大的收获,那么我们帮他计划一下吧,看看X最多能收获多少。

Input

 

第一行输入m(m < 10),表示有m组测试案例。

每个测试案例:

第一行有一个数字n , T(n < 100),表示Xn科课程要学习,和剩余的时间T

之后的n行,每行两个整数tst表示学习该科需要的时间,s表示学习该科能得到的收获。

Output

 

每个测试案例输出一行,输出X的最大收获sum(保留2为小数)

Sample Input

2
2 10
5 5
10 10
2 10
5 10
10 10

Sample Output

10.00
15.00

Hint

 

Source

winddreams