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

Как известно, большинство учеников и преподавателей ЛКШ большую часть года живут в Берляндии, в которой достаточно широко распространена коррупция. Поэтому рассмотрим следующий жизненный сюжет.

Скоро должны пройти выборы. Вы знаете количество избирателей и количество партий — $$$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$$$ не получит ни одного голоса.

В третьем тесте из условия Объединённая Партия может купить голоса первых трёх избирателей и выиграть, набрав три голоса против двух голосов у пятой партии.