E2. Голосование (усложнённая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — ограничения.

Сейчас в Берляндии проходят выборы и вы хотите победить в них. А точнее, вы не просто хотите победить, а сделать так, чтобы все проголосовали за вас.

Всего есть $$$n$$$ голосующих и два варианта сделать так, чтобы они проголосовали за вас. Первый вариант это заплатить $$$i$$$-му голосующему $$$p_i$$$ монет. Второй вариант, это сделать так, чтобы $$$m_i$$$ других людей проголосовало за вас, и тогда $$$i$$$-й голосующий проголосует бесплатно.

Более того, процесс такого голосования проходит в несколько шагов. Например, если есть пять голосующих $$$m_1 = 1$$$, $$$m_2 = 2$$$, $$$m_3 = 2$$$, $$$m_4 = 4$$$, $$$m_5 = 5$$$, то вы можете купить голос пятого, и в конце концов все проголосуют за вас. Множество людей, голосующих за вас, будет меняться следующим образом: $$${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}$$$.

Посчитайте минимально количество монет, которое вам нужно потратить, чтобы все проголосовали за вас.

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

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество наборов входных данных.

Первая строка каждого набора содержит число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество голосующих.

Следующие $$$n$$$ строк содержат описание голосующих. $$$i$$$-я строка содержит два числа $$$m_i$$$ и $$$p_i$$$ ($$$1 \le p_i \le 10^9, 0 \le m_i < n$$$).

Гарантируется, что сумма $$$n$$$ по всем тест-кейсам не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор выведите одно число — минимально количество монет, которое вам нужно потратить, чтобы все проголосовали за вас.

Пример
Входные данные
3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5
Выходные данные
8
0
7
Примечание

В первом наборе вам нужно купить голос третьего голосующего. Тогда множество людей, голосующих за вас, будет меняться следующим образом: $$${3} \rightarrow {1, 3} \rightarrow {1, 2, 3}$$$.

Во втором наборе вам не нужно покупать голоса. Множество людей, голосующих за вас, будет меняться следующим образом: $$${1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7}$$$.

В третьем наборе вам нужно купить голоса второго и пятого голосующих. Тогда множество людей, голосующих за вас, будет меняться следующим образом: $$${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$$$.