Арсений придумал очередной бизнес-план — продавать газировку в автомате! Для этого он приобрёл автомат с \(n\) полками, а также \(k\) бутылок, \(i\)-я бутылка характеризуется номером бренда \(b_i\) и стоимостью \(c_i\).
На каждую полку можно поставить сколько угодно бутылок, но все бутылки на одной полке должны быть одного и того же бренда.
Арсений знает, что все бутылки, которые он выставит на полки автомата, будут проданы. Поэтому он попросил вас вычислить, какую максимальную сумму он сможет заработать.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную сумму, которую может заработать Арсений.
Примечание
В первом наборе входных данных у Арсения \(3\) полки в автомате. Он может расположить, например, две бутылки бренда \(2\) на первой полке и бутылку бренда \(1\) на второй. Тогда суммарная стоимость бутылок будет равна \(6 + 7 + 15 = 28\).
Во втором наборе у него есть только одна полка. Нетрудно показать, что оптимальным вариантом будет разместить на ней бутылку бренда \(1\). Тогда суммарная стоимость будет равна \(15\).
В третьем наборе входных данных у него есть целых \(6\) полок, поэтому он может разместить все имеющиеся бутылки итоговой стоимостью \(7 + 5 = 12\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|