您有 $$$n$$$ 灯,按从 $$$1$$$ 到 $$$n$$$ 的整数编号。每个灯 $$$i$$$ 有两个整数参数 $$$a_i$$$ 和 $$$b_i$$$。
每个时刻,每个灯都处于三种状态之一:它可能打开、关闭或损坏。
最初所有灯都关闭。在一次操作中,您可以选择一盏关闭的灯并将其打开(无法打开损坏的灯)。打开灯 $$$i$$$ 即可获得 $$$b_i$$$ 积分。每次执行操作后都会发生以下情况:
- 让我们将打开的灯的数量表示为$$$x$$$(损坏的灯不计算在内)。所有灯 $$$i$$$ 使得 $$$a_i \le x$$$ 同时损坏,无论它们是打开还是关闭。
请注意,损坏的灯永远不会被视为打开,并且在打开的灯损坏后,您仍然保留因打开它而收到的积分。
您可以执行任意数量的操作。
找出你可以获得的最大分数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 灯的数量。
接下来的 $$$n$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le n, 1 \le b_i \le 10^9$$$) — 第 $$$i$$$ 个灯的参数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——您可以获得的最大分数。
示例
输入 #1
4 4 2 2 1 6 1 10 1 13 5 3 4 3 1 2 5 3 2 3 3 6 1 2 3 4 1 4 3 4 3 5 2 3 1 1 1
输出 #1
15 14 20 1
注意
在第一个测试用例中 $$$n = 4$$$。获得最大点数的方法之一如下:
- 您打开灯 $$$4$$$ 并获得 $$$b_4 = 13$$$ 积分。
- 打开的灯数量为 $$$1$$$,因此所有带有 $$$a_i \le 1$$$ 的灯(即灯 $$$2$$$、$$$3$$$ 和 $$$4$$$ 都会损坏。灯 $$$4$$$ 不再打开,因此打开的灯数量变为 $$$0$$$。
- 您唯一可以打开的灯是 $$$1$$$ 灯,因为所有其他灯都坏了。打开它,您将获得 $$$b_1 = 2$$$ 积分。
- 打开的灯数量为 $$$1$$$。由于 $$$a_1 = 2$$$,灯 $$$1$$$ 不会损坏。
您总共获得 $$$13 + 2 = 15$$$ 积分。可以看出,这是您可以获得的最大分数,因此第一个测试用例的答案是$$$15$$$。
在第二个测试用例中,获得最大点数的方法之一如下:
- 第一次操作时,您打开灯 $$$4$$$ 并获得 $$$2$$$ 积分。第一次操作后没有灯泡破裂。
- 在第二次操作中,您打开灯 $$$3$$$ 并获得 $$$5$$$ 积分。第二次操作后,有$$$2$$$灯亮起。当$$$a_3 \le 2$$$ 时,灯$$$3$$$ 坏了。
- 在第三次操作中,您打开灯 $$$1$$$ 并获得 $$$4$$$ 积分。
- 在第四次操作中,您打开灯 $$$5$$$ 并获得 $$$3$$$ 积分。之后,$$$3$$$ 灯打开:灯$$$1$$$、$$$4$$$ 和$$$5$$$。灯 $$$1$$$、$$$2$$$、$$$4$$$ 和 $$$5$$$ 同时损坏,因为对于所有灯 $$$a_i \le 3$$$。
您总共获得 $$$2 + 5 + 4 + 3 = 14$$$ 积分。可以证明这是你可以获得的最大点数。
在第三个测试用例中,获得最大点数的方法之一如下:
- 打开灯 $$$3$$$ 并获得 $$$4$$$ 积分。灯 $$$1$$$ 和 $$$3$$$ 坏了。
- 打开灯 $$$2$$$ 并获得 $$$4$$$ 积分。
- 打开灯 $$$6$$$ 并获得 $$$3$$$ 积分。灯 $$$6$$$ 坏了。
- 打开灯 $$$4$$$ 并获得 $$$4$$$ 积分。
- 打开灯 $$$5$$$ 并获得 $$$5$$$ 积分。灯 $$$2$$$、$$$4$$$ 和 $$$5$$$ 坏了。
您总共获得 $$$4 + 4 + 3 + 4 + 5 = 20$$$ 积分。可以证明这是你可以获得的最大点数。