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