CF1251E2 Voting (Hard Version)

简单版与困难版的唯一区别在于数据范围。 现在在 Berland 举行选举，你希望赢得选举。更准确地说，你希望每个人都投票给你。 共有 $n$ 个选民，你有两种方式说服每个选民投票给你。第一种方式是给第 $i$ 个选民 $p_i$ 枚金币。第二种方式是让 $m_i$ 个其他选民投票给你，这样第 $i$ 个选民就会免费投票给你。 此外，这种投票过程会分多步进行。例如，如果有五个选民，$m_1 = 1$，$m_2 = 2$，$m_3 = 2$，$m_4 = 4$，$m_5 = 5$，你可以先买下第 5 个选民的选票，最终所有人都会投票给你。投票给你的人集合变化如下：${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 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 < n$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示让所有人都投票给你所需花费的最少金币数。

第一个测试用例中，你需要买下第 3 个选民的选票。投票给你的人集合变化如下：${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 个选民的选票。投票给你的人集合变化如下：${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$。 由 ChatGPT 4.1 翻译