Как известно, большинство учеников и преподавателей ЛКШ большую часть года живут в Берляндии, в которой достаточно широко распространена коррупция. Поэтому рассмотрим следующий жизненный сюжет.
Скоро должны пройти выборы. Вы знаете количество избирателей и количество партий — \(n\) и \(m\) соответственно. Также, для каждого избирателя вы знаете, за какую партию он собирается голосовать. Однако, при наличии определённой суммы денег, это всё поправимо. В частности, если заплатить \(i\)-му избирателю \(c_i\) байткоинов, можно сделать так, чтобы тот проголосовал за любую партию по вашему усмотрению.
Объединённая Партия Государства Берляндии заказала у вас статистическое исследование — вам нужно выяснить минимальное количество байткоинов, которое ей нужно потратить, чтобы гарантировать себе победу. Чтобы партия выиграла выборы, ей необходимо набрать строго больше голосов, чем набрала любая из остальных партий.
Выходные данные
Выведите одно число — минимальное количество байткоинов, которое нужно заплатить избирателям, чтобы Объединённая Партия Государства Берляндии смогла победить.
Примечание
В первом тесте из условия Объединённая Партия выигрывает выборы, не покупая голоса избирателей.
Во втором тесте из условия Объединённая Партия может перекупить голоса первого и четвёртого избирателя. Таким образом, она наберёт два голоса, партии номер \(3\), \(4\) и \(5\) по одному, партия номер \(2\) не получит ни одного голоса.
В третьем тесте из условия Объединённая Партия может купить голоса первых трёх избирателей и выиграть, набрав три голоса против двух голосов у пятой партии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
1 100
|
0
|
|
2
|
5 5
2 100
3 200
4 300
5 400
5 900
|
500
|
|
3
|
5 5
2 100
3 200
4 300
5 800
5 900
|
600
|