- Все сделали ставку? Я брошу кубик уже через минуту!

У дилера есть $k$-гранный кубик. За столом сидит $n$ игроков. Перед началом игры каждый игрок ставит произвольное количество фишек на одну из граней кубика.

Когда все сделали ставку, дилер $n$ раз бросает кубик. $i$-тый бросок определяет судьбу ставки $i$-того игрока. Если выпадает грань, которую загадал игрок, дилер увеличивает его ставку в $k$ раз и возвращает игроку. В противном случае дилер забирает ставку игрока себе.

Дилер настолько ловкий, что способен выкинуть на кубике любую грань, какую захочет, но должен соблюдать правило «случайного распределения»: если за столом сидит $n$ участников, то за один круг каждая грань должна выпасть ровно $\frac{n}{k}$ раз ($n$ всегда кратно $k$), иначе игроки взбунтуются и спросят, кто вы такой, чтоб это сделать.

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

Входные данные

В первой строке находятся числа $n$ и $k$ ($2 \le k \le n \le 10^5$, $n$ кратно $k$) – количество участников, сидящих за столом и количество граней у кубика дилера.

В следующих $n$ строках находятся по два целых числа $w_i$ ($1 \le w_i \le k$) и $a_i$ ($1 \le a_i \le 30$) - номер грани, на которую ставит $i$-тый игрок и его ставка в фишках соответственно.

Выходные данные

Выведите одно число: максимальную прибыль в фишках, которую может получить дилер. Если в лучшем случае дилер уходит в минус, число может быть отрицательным.

Подзадачи