Codeforces Round 984 (Div. 3) |
---|
Закончено |
Арсений придумал очередной бизнес-план — продавать газировку в автомате! Для этого он приобрёл автомат с $$$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$$$.
Для каждого набора входных данных выведите одно целое число — максимальную сумму, которую может заработать Арсений.
43 32 62 71 151 32 62 71 156 21 72 5190000 11 1000
28 15 12 1000
В первом наборе входных данных у Арсения $$$3$$$ полки в автомате. Он может расположить, например, две бутылки бренда $$$2$$$ на первой полке и бутылку бренда $$$1$$$ на второй. Тогда суммарная стоимость бутылок будет равна $$$6 + 7 + 15 = 28$$$.
Во втором наборе у него есть только одна полка. Нетрудно показать, что оптимальным вариантом будет разместить на ней бутылку бренда $$$1$$$. Тогда суммарная стоимость будет равна $$$15$$$.
В третьем наборе входных данных у него есть целых $$$6$$$ полок, поэтому он может разместить все имеющиеся бутылки итоговой стоимостью $$$7 + 5 = 12$$$.
Название |
---|