Спасатели (Платина)
Фермер Джон открыл бассейн для своих коров, полагая, что это поможет им расслабиться и произвести больше молока.
Чтобы обеспечить безопасность, он нанимает n коров в качестве спасателей, у каждой из которых есть смена, охватывающая некоторый непрерывный промежуток времени в течение дня. Для простоты пул открыт с момента времени 0 до 10^9 ежедневно, поэтому каждую смену можно описать двумя целыми числами - время, когда корова начинает и заканчивает свою смену. Например, спасатель, начинающий в момент времени t = 4 и заканчивающий в момент времени t = 7, охватывает три единицы времени (обратите внимание, что конечные точки - это "точки" во времени).
К сожалению, фермер Джон нанял на k спасателей больше, чем у него имеется средств на их содержание. Учитывая, что он должен уволить ровно k спасателей, каково максимальное количество времени, которое еще можно покрыть сменами оставшихся спасателей? Промежуток времени покрывается, если присутствует хотя бы один спасатель.
Входные данные
Первая строка содержит n и k (k ≤ n ≤ 100000, 1 ≤ k ≤ 100). Каждая из следующих n строк описывает спасателя в виде двух целых чисел в диапазоне 0..10^9 - начальная и конечная точки смены спасателя. Все точки различны. Смены разных спасателей могут пересекаться.
Выходные данные
Выведите максимальное количество времени, которое может быть покрыто, если фермер Джон уволит k спасателей.
Пример
ФД должен уволить спасателей покрывающих 1..8 и 7..15.