B. Лампочки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — наибольшее количество очков, которое вы можете набрать.

Пример
Входные данные
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$$$ и получаете $$$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$$$ очков. Можно показать, что это наибольшее количество очков, которое можно набрать.