Preparing NOJ

Roundgod and Milk Tea

6000ms 131072K


Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festival. There will be $$$n$$$ classes participating in this festival, where the $$$i$$$th class has $$$a_i$$$ students and will make $$$b_i$$$ cups of milk tea.

Roundgod wants more students to savor milk tea, so he stipulates that every student can taste at most one cup of milk tea. Moreover, a student can't drink a cup of milk tea made by his class. The problem is, what is the maximum number of students who can drink milk tea?


The first line of input consists of a single integer $$$T$$$ $$$(1 \leq T \leq 25)$$$, denoting the number of test cases.

Each test case starts with a line of a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$, the number of classes. For the next $$$n$$$ lines, each containing two integers $$$a, b$$$ $$$(0 \leq a, b \leq 10^9)$$$, denoting the number of students of the class and the number of cups of milk tea made by this class, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$6 \times 10^6$$$.


For each test case, print the answer as a single integer in one line.

Sample Input:

3 4
2 1

Sample Output:




Provider HDU

Origin HDU855-1011

Code HDU6667


Submitted 154

Passed 15

AC Rate 9.74%

Date 08/14/2019 12:03:16


Nothing Yet