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

Арсений придумал очередной бизнес-план — продавать газировку в автомате! Для этого он приобрёл автомат с $$$n$$$ полками, а также $$$k$$$ бутылок, $$$i$$$-я бутылка характеризуется номером бренда $$$b_i$$$ и стоимостью $$$c_i$$$.

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

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

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

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

Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$), где $$$n$$$ — количество полок в автомате, а $$$k$$$ — количество бутылок в распоряжении Арсения.

Следующие $$$k$$$ строк содержат по два целых числа $$$b_i$$$ и $$$c_i$$$ ($$$1 \le b_i \le k, 1 \le c_i \le 1000$$$) — бренд и стоимость $$$i$$$-й бутылки.

Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$ и что сумма $$$k$$$ по всем наборам входных данных также не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
3 3
2 6
2 7
1 15
1 3
2 6
2 7
1 15
6 2
1 7
2 5
190000 1
1 1000
Выходные данные
28
15
12
1000
Примечание

В первом наборе входных данных у Арсения $$$3$$$ полки в автомате. Он может расположить, например, две бутылки бренда $$$2$$$ на первой полке и бутылку бренда $$$1$$$ на второй. Тогда суммарная стоимость бутылок будет равна $$$6 + 7 + 15 = 28$$$.

Во втором наборе у него есть только одна полка. Нетрудно показать, что оптимальным вариантом будет разместить на ней бутылку бренда $$$1$$$. Тогда суммарная стоимость будет равна $$$15$$$.

В третьем наборе входных данных у него есть целых $$$6$$$ полок, поэтому он может разместить все имеющиеся бутылки итоговой стоимостью $$$7 + 5 = 12$$$.