#P1251E2. Voting (Hard Version)

    ID: 2142 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchdata structuresgreedy*2400

Voting (Hard Version)

Description

The only difference between easy and hard versions is constraints.

Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you.

There are nn voters, and two ways to convince each of them to vote for you. The first way to convince the ii-th voter is to pay him pip_i coins. The second way is to make mim_i other voters vote for you, and the ii-th voter will vote for free.

Moreover, the process of such voting takes place in several steps. For example, if there are five voters with m1=1m_1 = 1, m2=2m_2 = 2, m3=2m_3 = 2, m4=4m_4 = 4, m5=5m_5 = 5, then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: 51,51,2,3,51,2,3,4,5{5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}.

Calculate the minimum number of coins you have to spend so that everyone votes for you.

The first line contains one integer tt (1t21051 \le t \le 2 \cdot 10^5) — the number of test cases.

The first line of each test case contains one integer nn (1n21051 \le n \le 2 \cdot 10^5) — the number of voters.

The next nn lines contains the description of voters. ii-th line contains two integers mim_i and pip_i (1pi109,0mi<n1 \le p_i \le 10^9, 0 \le m_i < n).

It is guaranteed that the sum of all nn over all test cases does not exceed 21052 \cdot 10^5.

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.

Input

The first line contains one integer tt (1t21051 \le t \le 2 \cdot 10^5) — the number of test cases.

The first line of each test case contains one integer nn (1n21051 \le n \le 2 \cdot 10^5) — the number of voters.

The next nn lines contains the description of voters. ii-th line contains two integers mim_i and pip_i (1pi109,0mi<n1 \le p_i \le 10^9, 0 \le m_i < n).

It is guaranteed that the sum of all nn over all test cases does not exceed 21052 \cdot 10^5.

Output

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.

Samples

样例输入 1

3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5

样例输出 1

8
0
7

Note

In the first test case you have to buy vote of the third voter. Then the set of people voting for you will change as follows: 31,31,2,3{3} \rightarrow {1, 3} \rightarrow {1, 2, 3}.

In the second example you don't need to buy votes. The set of people voting for you will change as follows: 11,3,51,2,3,51,2,3,5,6,71,2,3,4,5,6,7{1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7}.

In the third test case you have to buy votes of the second and the fifth voters. Then the set of people voting for you will change as follows: 2,51,2,3,4,51,2,3,4,5,6{2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}.