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

Задача состоит из трех подзадач: за решение подзадачи С1 вы получите 4 балла, за решение подзадачи С2 вы получите 4 балла, за решение подзадачи C3 вы получите 8 баллов.

Манао решил заняться борьбой на профессиональном уровне. Для своего дебюта он избрал уже начавшийся турнир. До того, как Манао вступил в него, в турнире было n участников, пронумерованных от 1 до n. У каждого из них было некоторое количество очков. Более конкретно, у i-го участника было pi очков.

Манао будет бороться с каждым из участников ровно один раз. Каждый из поединков заканчивается для него или победой, или поражением. Каждая победа Манао прибавляет к его счету 1 очко, а каждое его поражение прибавляет 1 очко к счету соответствующего противника. Для каждого i, Манао определил степень усилий ei, которую ему нужно приложить, что победить в бою против i-го участника. Проиграть бой усилий не требует.

После окончания всех боев с участием Манао будет сгенерирована турнирная таблица. Стандартно, самое лучшее место в турнирной таблице — первое, а самое худшее — место n + 1. Участники турнира будут упорядочены по убыванию набранных ими очков. Участники, имеющие равный счет с Манао, будут иметь ранг лучше него, если их единственный бой закончился поражением Манао, и хуже в противном случае. Как именно производится ранжировка других участников с одинаковым количеством очков, для этой задачи значения не имеет.

Цель Манао — получить место k или лучше. Определите минимальную суммарную степень усилий, которую ему надо приложить для достижения своей цели, если это вообще возможно.

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

В первой строке записаны два целых числа n и k (1 ≤ k ≤ n + 1). Затем следует n строк, каждая из которых содержит пару целых чисел, записанных через пробел — pi и ei (0 ≤ pi, ei ≤ 200000).

Задача состоит из трех подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже.

  • В подзадаче C1 (4 балла) ограничение на n: 1 ≤ n ≤ 15.
  • В подзадаче C2 (4 балла) ограничение на n: 1 ≤ n ≤ 100.
  • В подзадаче C3 (8 баллов) ограничение на n: 1 ≤ n ≤ 200000.
Выходные данные

В единственной строке выведите целое число — наименьшую суммарную степень усилий, которую Манао нужно приложить, чтобы попасть в лучшие k бойцов. Если Манао не может попасть в лучшие k бойцов, выведите число -1.

Примеры
Входные данные
3 2
1 1
1 4
2 2
Выходные данные
3
Входные данные
2 1
3 2
4 0
Выходные данные
-1
Входные данные
5 2
2 10
2 10
1 1
3 1
3 1
Выходные данные
12
Примечание

Рассмотрим первый пример. В момент вступления Манао в турнир, в нем уже участвует три бойца. Первый из них набрал 1 турнирное очко, а победа над ним потребует 1 единицу усилий Манао. Второй участник также имеет одно очко, но победа над ним стоит Манао 4 единицы усилий. У третьего участника 2 очка, а для победы над ним нужно приложить 2 единицы усилий. Манао хочет получить место 2 или выше. Оптимальным решением является выиграть у бойцов 1 и 3, после чего Манао и участники под номерами 2 и 3 будут иметь по два очка. Манао будет выигрывать в турнирной таблице у бойца 3 и проигрывать бойцу 2, таким образом занимая второе место.

Во втором примере, даже если Манао одержит победу в обоих поединках, он все равно останется на третьем месте.