CF1839B Lamps

你有 $n$ 盏灯，编号为 $1$ 到 $n$。每盏灯 $i$ 有两个整数参数 $a_i$ 和 $b_i$。 每一时刻，每盏灯有三种状态：开、关或损坏。 初始时所有灯都是关闭的。每次操作，你可以选择一盏关闭的灯将其打开（不能打开已损坏的灯）。打开第 $i$ 盏灯你会获得 $b_i$ 分。每次操作后会发生以下情况： - 设当前被打开的灯的数量为 $x$（不计损坏的灯）。所有满足 $a_i \le x$ 的灯 $i$ 会同时损坏，无论它们是开着还是关着。 请注意，损坏的灯不计入已打开的灯数量，并且一旦已打开的灯损坏，你仍然保留因打开它获得的分数。 你可以进行任意次数的操作。 请你求出你能获得的最大分数。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示你能获得的最大分数。

在第一个测试用例中，$n=4$。一种获得最大分数的方法如下： - 你先打开第 $4$ 盏灯，获得 $b_4=13$ 分。 - 当前被打开的灯数量为 $1$，所以所有 $a_i \le 1$ 的灯（即第 $2$、$3$、$4$ 盏灯）会损坏。第 $4$ 盏灯不再计入已打开的灯，所以当前被打开的灯数量变为 $0$。 - 你只能打开第 $1$ 盏灯，其余灯已损坏。你打开第 $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$ 盏灯。由于 $a_i \le 3$，第 $1$、$2$、$4$、$5$ 盏灯同时损坏。 你总共获得 $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$ 分。可以证明这是最大分数。 由 ChatGPT 4.1 翻译