Фермер Джон открыл бассейн для своих коров, чтобы они там отдыхали и потом
давали больше молока.
Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из
которых работает в течение некоторого интервала времени в течение дня.
Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(10^9\)
каждый день. Поэтому каждый интервал может быть описан двумя целыми числами
- временем начала и конца работы спасателя. Например, спасатель, начинающий в
момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает
интервал в три единицы времени.
К несчастью, ФД нанял на \(K\) спасателей больше чем может платить зарплату.
При условии, что он должен уволить ровно \(K\) спасателей, какой максимальный интервал
времени, будет покрыт оставшимися спасателями? Интервал времени покрыт, если
присутствует хоть один спасатель в это время.
ФОРМАТ ВВОДА (файл lifeguards.in):
Первая строка ввода содержит два числа \(N\) и \(K\)
(\(K \leq N \leq 100,000, 1 \leq K \leq 100\)). Каждая из последующих
\(N\) строк описывает интервалы работы спасателей двумя целыми числами в интервале
\(0 \ldots 10^9\), задающими начало и конец работы спасателя. Все числа концы
интервалов - различны. Сами интервалы могут перекрываться.
ФОРМАТ ВЫВОДА (файл lifeguards.out):
Выведите одно целое число - максимальное количество времени, которое останется
покрытым, если ФД уволит \(K\) спасателей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 8
7 15
2 14
|
12
|