Домашки с дедлайнами

В школе на четверть дали много небольших работ. Каждая работа занимает ровно один день: если ты делаешь её в какой-то день, то в этот день ты больше ничего не успеваешь.

За работу i дают p_i баллов, но только если закончить её не позже дня d_i (то есть выбрать для неё день t, где 1 ≤ t ≤ d_i). В один день можно сделать не больше одной работы. Некоторые работы можно не делать.

Найди максимальную сумму баллов, которую можно набрать.

Важно: сумма баллов может не помещаться в 32-битный тип (как на олимпиадах). В Python это не проблема, но в других языках нужен 64-битный тип.

Формат ввода

Первая строка содержит целое число t — количество наборов данных.

Далее идут t наборов данных. Каждый набор начинается с целого числа n — количества работ.

Далее идут n строк, в каждой два целых числа p_i и d_i — баллы за работу и последний день, когда её ещё можно сдать.

Формат вывода

Для каждого набора данных выведи одно целое число — максимальную возможную сумму баллов. Ответы выводятся по одному в строке.

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ n ≤ 100000
• Сумма значений n по всем наборам данных не превышает 100000.
• 1 ≤ p_i ≤ 1000000
• 1 ≤ d_i ≤ 200000

Пример

Ввод:

3
1
1 1
2
5 1
6 1
3
10 1
9 2
8 3

Вывод:

1
6
27