CF1251E2.Voting (Hard Version)

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.

简单版本与困难版本的唯一区别在于约束条件。

现在 Berland 正在举行选举，你希望赢得这场选举。更准确地说，你希望所有人都为你投票。

共有 $n$ 名选民，说服其中第 $i$ 名选民为你投票有两种方式：

• 第一种方式是向其支付 $p_i$ 枚硬币；
• 第二种方式是让其他 $m_i$ 名选民先为你投票，则第 $i$ 名选民将免费为你投票。

此外，这种投票过程是分若干步进行的。例如，若存在五名选民，且 $m_1 = 1$、$m_2 = 2$、$m_3 = 2$、$m_4 = 4$、$m_5 = 5$，则你可以购买第五名选民的选票，最终所有人将为你投票。为你投票的人集合将按如下顺序变化：
${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}$。

请计算你至少需要花费多少枚硬币，才能使所有选民都为你投票。

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 \lt n$).

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

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^5$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 选民的数量。

接下来的 $n$ 行描述了各个选民。第 $i$ 行包含两个整数 $m_i$ 和 $p_i$（$1 \le p_i \le 10^9,\ 0 \le m_i \lt n$）。

保证所有测试用例的 $n$ 之和不超过 $2 \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.

对于每个测试用例，输出一个整数——即你需要花费的最少硬币数量，使得所有人都为你投票。

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}$.

在第一个测试用例中，你需要收买第三位选民的选票。此时支持你的人员集合将按如下方式变化：${3} \rightarrow {1, 3} \rightarrow {1, 2, 3}$。

在第二个例子中，你无需收买任何选票。此时支持你的人员集合将按如下方式变化：${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}$。

在第三个测试用例中，你需要收买第二位和第五位选民的选票。此时支持你的人员集合将按如下方式变化：${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$。