Voting (Hard Version)
Contest: Educational Codeforces Round 75 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, greedy

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 $$$n$$$ voters, and two ways to convince each of them to vote for you. The first way to convince the $$$i$$$-th voter is to pay him $$$p_i$$$ coins. The second way is to make $$$m_i$$$ other voters vote for you, and the $$$i$$$-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 $$$m_1 = 1$$$, $$$m_2 = 2$$$, $$$m_3 = 2$$$, $$$m_4 = 4$$$, $$$m_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: $$${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.

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

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

The next $$$n$$$ lines contains the description of voters. $$$i$$$-th line contains two integers $$$m_i$$$ and $$$p_i$$$ ($$$1 \le p_i \le 10^9, 0 \le m_i < n$$$).

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

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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: $$${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: $$${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, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$$$.

Example input:
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

Example output:
8
0
7

Editorial:
Denote the number of voters with $$$m_i = x$$$ as $$$c_x$$$. Also denote $$$pref_x = \sum\limits_{i=0}^{x-1} c_x$$$, i.e. $$$pref_x$$$ is equal to number of voters with $$$m_i < x$$$.
Let's group all voters by value $$$m_i$$$. We'll consider all these group in decreasing value of $$$m_i$$$. Assume that now we consider group with $$$m_i = x$$$. Then there are two cases:
1. if $$$pref_{x} + cnt \ge x$$$ then all these voters will vote for you for free. $$$cnt$$$ is equal to the number of votes bought in previous steps;
2. if $$$pref_{x} + cnt < x$$$ then we have to buy $$$x - pref_{s} - cnt$$$ additional votes. Moreover the value $$$m_i$$$ of this "bought" voter must be greater than or equal to $$$x$$$. Since these voters indistinguishable we have to buy $$$x - pref_{s} - cnt$$$ cheapest voter (with a minimal value of $$$p_i$$$).
So, all we have to do it maintain values $$$p_i$$$ not yet bought voters in some data structure (for example multiset in C++).