E. Телефонные разговоры
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Недавно Сережа стал бизнесменом Сергеем Петровичем, и теперь ему приходится много разговаривать по телефону. На сегодня у него запланировано n звонков. Для каждого звонка известен запланированный момент его начала ti (в секундах от начала дня) и его продолжительность di (в секундах). Все ti различны. Сергей Петрович — очень важный человек, сам он никому не звонит, и все его звонки будут входящими.

Сергей Петрович не Цезарь, сразу несколько дел делать не умеет. Поэтому, если ему звонят, пока он еще не закончил предыдущий разговор, то он ставит новый звонок в очередь на удержание. В таком случае немедленно после окончания текущего разговора он берет из очереди самый ранний входящий звонок и начинает этот разговор. Если Сергей Петрович начал разговор в секунду t, а звонок продолжается d секунд, то он занят в секунды t, t + 1, ..., t + d - 1, а в секунду t + d он может начать новый звонок. Если Сергей Петрович не занят разговором в момент поступления очередного звонка, он не может отправить его в очередь.

Кроме того, Сергей Петрович не Наполеон, он любит поспать. Поэтому иногда он позволяет себе проигнорировать звонок, как будто его вовсе не было. Так он может поступить не более k раз. Звонок, поступающий во время разговора, тоже можно проигнорировать.

Какое наибольшее время в секундах сможет сегодня поспать Сергей Петрович, если он может выделить на сон любой непрерывный отрезок времени текущих суток (то есть с секундами от 1-ой до 86400-ой включительно), не занятый разговорами?

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

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

В первой строке входных данных записана пара целых чисел n, k (0 ≤ k ≤ n ≤ 4000), разделенных единичным пробелом. Далее в n строках содержатся описания звонков на сегодня. Описание каждого звонка содержится в отдельной строке и состоит из двух целых чисел ti и di, записанных через пробел (1 ≤ ti, di ≤ 86400). Все ti различны, звонки заданы в порядке строгого возрастания ti.

Запланированные времена звонков [ti, ti + di - 1] могут произвольным образом пересекаться.

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

Выведите число от 0 до 86400 включительно — наибольшее возможное количество секунд для сна Сергея Петровича на сегодня.

Примеры
Входные данные
3 2
30000 15000
40000 15000
50000 15000
Выходные данные
49999
Входные данные
5 1
1 20000
10000 10000
20000 20000
25000 10000
80000 60000
Выходные данные
39999
Примечание

В первом примере лучше всего проигнорировать первые два звонка.

Во втором примере лучше всего проигнорировать третий звонок. В этом случае Сергей Петрович будет разговаривать:

  • первый звонок: с 1 по 20000-ую секунду,
  • второй звонок: с 20001 по 30000-ую секунду,
  • четвертый звонок: с 30001 по 40000-ую секунду (третий звонок полностью игнорируется),
  • пятый звонок: с 80000 по 139999-ую секунду.

Таким образом, самый длинный период свободного времени — с 40001-ой секунды по 79999-ую.