Рятувальники (Платина)
Фермер Джон вирішив відкрити басейн для своїх корів, сподіваючись, що це допоможе їм розслабитися і збільшити виробництво молока.
Для забезпечення безпеки він наймає 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.