小坑坑堆砖头

Time Limit: 5000MS

Memory Limit: 131072KB

Description

小坑坑觉得堆砖头太坑了,于是想要破解了这个游戏。

小坑坑有一堆砖头,每个砖头都有两个属性,一个是他的质量,一个是他所能承受的质量。

现在小坑坑想要将这些砖头尽可能地堆起一堆,使其总质量最大。


PS:质量小的砖头只能放在质量大于等于的砖头上面,如果一个砖头上面所放砖头的总质量大于了该砖头所能承受的质量,则该砖头会破碎。

Input

输入一个整数T(T<=10),表示样例的个数,接下来输入整数n,表示n(n<=30)个砖头,接下来输入n行,每行分别有两个数m1,m2(m1 <= 50 , m2<= 1500),分别表示每个砖块自己的质量和所能承受的质量。


Output

每个样例分别输出他所堆出的最大质量。


Sample Input

1
3
5 6
4 5
3 2

Sample Output

9

Hint

None

Source

skt

提交代码