简单版本和困难版本之间的唯一区别是限制。
现在 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}$$$。
计算你必须花费的最少硬币数量,以便每个人都投票给你。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 您必须花费的最少硬币数量,以便每个人都投票给您。
示例
输入 #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
注意
在第一个测试用例中,您必须购买第三个投票者的投票。那么投票给你的人的集合将发生如下变化:$$${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}$$$。