CF1839B.Lamps

You have $n$ lamps, numbered by integers from $1$ to $n$. Each lamp $i$ has two integer parameters $a_i$ and $b_i$.

At each moment each lamp is in one of three states: it may be turned on, turned off, or broken.

Initially all lamps are turned off. In one operation you can select one lamp that is turned off and turn it on (you can't turn on broken lamps). You receive $b_i$ points for turning lamp $i$ on. The following happens after each performed operation:

• Let's denote the number of lamps that are turned on as $x$ (broken lamps do not count). All lamps $i$ such that $a_i \le x$ simultaneously break, whether they were turned on or off.

Please note that broken lamps never count as turned on and that after a turned on lamp breaks, you still keep points received for turning it on.

You can perform an arbitrary number of operations.

Find the maximum number of points you can get.

你有 $n$ 盏灯，编号为从 $1$ 到 $n$ 的整数。每盏灯 $i$ 有两个整数参数 $a_i$ 和 $b_i$。

在任意时刻，每盏灯处于以下三种状态之一：开启、关闭或损坏。

初始时所有灯均处于关闭状态。每次操作中，你可以选择一盏当前处于关闭状态的灯并将其开启（不能开启已损坏的灯）。开启灯 $i$ 会为你获得 $b_i$ 分。每次执行完一次操作后，会发生如下事件：

• 设当前处于开启状态的灯的数量为 $x$（损坏的灯不计入此数量）。那么所有满足 $a_i \le x$ 的灯 $i$ 将同时损坏，无论其此前是开启还是关闭状态。

请注意：损坏的灯永远不被计为开启状态；并且，若一盏已开启的灯随后损坏，你仍保留此前开启它所获得的分数。

你可以执行任意次数的操作。

求你能获得的最大分数。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of lamps.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n, 1 \le b_i \le 10^9$) — parameters of the $i$-th lamp.

It is guaranteed that sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

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

For each test case, output one integer — the maximum number of points you can get.

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

In first test case $n = 4$. One of ways to get the maximum number of points is as follows:

• You turn lamp $4$ on and receive $b_4 = 13$ points.
• The number of lamps that are turned on is $1$, so all lamps with $a_i \le 1$ (namely lamps $2$, $3$ and $4$) break. Lamp $4$ is no longer turned on, so the number of lamps that are turned becomes $0$.
• The only lamp you can turn on is lamp $1$, as all other lamps are broken. You receive $b_1 = 2$ points for turning it on.
• The number of lamps that are turned on is $1$. As $a_1 = 2$, lamp $1$ doesn't break.

Your receive $13 + 2 = 15$ points in total. It can be shown that this is the maximum number of points you can get, so the answer for the first test case is $15$.

In the second test case, one of the ways to get the maximum number of points is as follows:

• On the first operation you turn on lamp $4$ and receive $2$ points. No lamps break after the first operation.
• On the second operation you turn on lamp $3$ and receive $5$ points. After the second operation, there are $2$ lamps turned on. As $a_3 \le 2$, lamp $3$ breaks.
• On the third operation, you turn on lamp $1$ and receive $4$ points.
• On the fourth operation, you turn on lamp $5$ and receive $3$ points. After that there are $3$ lamps turned on: lamps $1$, $4$ and $5$. Lamps $1$, $2$, $4$ and $5$ simultaneously break, because for all of them $a_i \le 3$.

You receive $2 + 5 + 4 + 3 = 14$ points in total. It can be shown that this is the maximum number of points you can get.

In the third test case, one of the ways to get the maximum number of points is as follows:

• Turn the lamp $3$ on and receive $4$ points. Lamps $1$ and $3$ break.
• Turn the lamp $2$ on and receive $4$ points.
• Turn the lamp $6$ on and receive $3$ points. Lamp $6$ breaks.
• Turn the lamp $4$ on and receive $4$ points.
• Turn the lamp $5$ on and receive $5$ points. Lamps $2$, $4$ and $5$ break.

You receive $4 + 4 + 3 + 4 + 5 = 20$ points in total. It can be shown that this is the maximum number of points you can get.

在第一个测试用例中，$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$ 分。可以证明这是你能获得的最大分数。