Рятувальники (Платина)#10426

Рятувальники (Платина)

1 секунда

128 мегабайтів

Легка

Фермер Джон відкрив для своїх корів басейн, вирішивши, що це допоможе їм розслабитися і давати більше молока.

Щоб забезпечити безпеку, він наймає $n$ корів рятувальниками, кожна з яких працює у зміну, що охоплює неперервний проміжок часу протягом дня. Для простоти вважатимемо, що басейн відкритий щодня з моменту часу $0$ до моменту часу $1 0^{9}$ 10^9, тому кожну зміну можна описати двома цілими числами: моментами початку і закінчення зміни корови. Наприклад, рятувальник, який починає зміну в момент $t = 4$ t = 4 і закінчує в момент $t = 7$ t = 7, покриває три одиниці часу (кінці зміни позначають моменти часу).

На жаль, фермер Джон найняв на $k$ рятувальників більше, ніж може собі дозволити оплачувати. Враховуючи, що він повинен звільнити рівно $k$ рятувальників, яка максимальна кількість часу, яку все ще можуть покрити зміни решти рятувальників? Момент часу вважається покритим, якщо на чергуванні перебуває принаймні один рятувальник.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $k (1 \leq k \leq 100, k \leq n \leq 1 0^{5})$ k~(1 \le k \le 100, k \le n \le 10^5). Кожен з наступних $n$ рядків містить два цілих числа $s_{i}$ s_i і $t_{i} (0 \leq s_{i} < t_{i} \leq 1 0^{9})$ t_i~(0 \le s_i < t_i \le 10^9) — моменти початку і закінчення зміни $i$ -го рятувальника. Усі кінці змін різні. Зміни різних рятувальників можуть перетинатися.

Вихідні дані

Виведіть максимальну кількість часу, яка все ще може бути покрита після того, як фермер Джон звільнить $k$ рятувальників.

Приклади

Приклад 1

Примітка

Фермеру Джону слід звільнити рятувальників, чиї зміни — $[1, 8]$ і $[7, 15]$ .