Lamps

Description:

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.

Sample Input:

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

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