/ StarOI / 题库 /

Bob and Alice

Bob and Alice

Bob and Alice

Description

Bob and Alice are planning a trip to NN cities after the final exam. But they don't have any money at all, so they have to do some work to earn money at each city.

Bob knows exactly that, at the ii-th city, they can spend at most aia_i money for fun (definitely they can only spend money on hand and cannot give credit), and then they will work and earn bib_i money. (Note that they'll always have fun first before working.)

Since they want the trip to be fun, they are going to spend as much money as possible.

Now Bob is boasting to Alice. "You know what? I can arrange the order of the cities we visit so that we can enjoy a best trip!'' Of course Alice doesn't believe in Bob because he always brags, and she is right. To avoid getting Alice disappointed again, Bob asks you to help him out.

Input

There are multiple test cases. The first line is an integer TT denoting the number of test cases.

For each test case, the first line is an integer NN (1N1000001\le N \le 100000) indicating the number of cities, and then NN lines follow, each line contains two integer aia_i and bib_i separated by a blank space (0ai,bi100000\le a_i,b_i \le 10000). It is guaranteed that the sum of all NN does not exceed 50000005000000.

Output

For each test case you shall output one line containing one number SS, which is the maximum money they can spend if they arrange NN cities in an optimal order.

Sample Case

Input

2
1
1 2
2
1 0
1 1

Output

0
1

信息

难度
8
分类
贪心 点击显示
标签
(无)
递交数
19
已通过
3
通过率
16%
上传者