310472: CF1839B. Lamps

B. Lampstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

15
14
20
1

Note

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.

题目大意：
你有一些编号为1到n的灯泡，每个灯泡有两个整数参数a_i和b_i。灯泡可以处于三种状态之一：开启、关闭或损坏。最初所有灯泡都是关闭的。你可以选择一个关闭的灯泡并开启它（不能开启已损坏的灯泡），开启灯泡i会获得b_i点数。每次操作后，如果开启的灯泡数量为x，那么所有a_i <= x的灯泡都会损坏。请注意，损坏的灯泡不计入开启数量，且开启后损坏的灯泡，你仍保留因开启它而获得的点数。你可以执行任意次数的操作。求你能获得的最大点数。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5），表示灯泡的数量。
- 接下来的n行，每行包含两个整数a_i和b_i（1 ≤ a_i ≤ n, 1 ≤ b_i ≤ 10^9），表示第i个灯泡的参数。
- 所有测试用例的n之和不超过2 × 10^5。

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

示例输入输出：
输入：
```
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
```
输出：
```
15
14
20
1
```

注意：
- 在第一个测试用例中，n = 4。获得最大点数的一种方式是：开启灯泡4获得13点，然后灯泡2、3和4损坏，再开启灯泡1获得2点，总共获得15点。
- 在第二个测试用例中，获得最大点数的一种方式是：依次开启灯泡4、3、1和5，总共获得14点。
- 在第三个测试用例中，获得最大点数的一种方式是：依次开启灯泡3、2、6、4和5，总共获得20点。题目大意： 你有一些编号为1到n的灯泡，每个灯泡有两个整数参数a_i和b_i。灯泡可以处于三种状态之一：开启、关闭或损坏。最初所有灯泡都是关闭的。你可以选择一个关闭的灯泡并开启它（不能开启已损坏的灯泡），开启灯泡i会获得b_i点数。每次操作后，如果开启的灯泡数量为x，那么所有a_i <= x的灯泡都会损坏。请注意，损坏的灯泡不计入开启数量，且开启后损坏的灯泡，你仍保留因开启它而获得的点数。你可以执行任意次数的操作。求你能获得的最大点数。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5），表示灯泡的数量。 - 接下来的n行，每行包含两个整数a_i和b_i（1 ≤ a_i ≤ n, 1 ≤ b_i ≤ 10^9），表示第i个灯泡的参数。 - 所有测试用例的n之和不超过2 × 10^5。 输出： - 对于每个测试用例，输出一个整数，表示你能获得的最大点数。 示例输入输出： 输入： ``` 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 ``` 输出： ``` 15 14 20 1 ``` 注意： - 在第一个测试用例中，n = 4。获得最大点数的一种方式是：开启灯泡4获得13点，然后灯泡2、3和4损坏，再开启灯泡1获得2点，总共获得15点。 - 在第二个测试用例中，获得最大点数的一种方式是：依次开启灯泡4、3、1和5，总共获得14点。 - 在第三个测试用例中，获得最大点数的一种方式是：依次开启灯泡3、2、6、4和5，总共获得20点。