Розклад#1768

Розклад

2 секунди

256 мегабайтів

Середня

Одного разу Арсеній приїхав до університету й, подивившись на розклад, дізнався, що сьогодні проходить рівно $N$ лекцій. Також він дізнався час початку й закінчення кожної лекції, а ще імена лекторів. Тепер він замислився — на які лекції йому варто сходити? Оскільки в Арсенія лише один зошит, він не може відвідати більше ніж $K$ різних лекцій, інакше йому буде нікуди записувати конспекти. Лекції проходять у різних аудиторіях, тож у будь-який момент часу Арсеній може бути присутнім не більше ніж на одній лекції. Проте він може залишити будь-яку лекцію в будь-який час, навіть до її завершення, і також може прийти після початку.

За кожну хвилину, проведену на лекції, Арсеній отримує $1$ бал знань. Звісно, він хоче максимізувати сумарну кількість знань, отриманих за день. Допоможіть Арсенію досягти цієї мети.

Арсеній чудово орієнтується у своєму факультеті, тому час на пересування між аудиторіями можна знехтувати.

Вхідні дані

У першому рядку задано два цілих числа $N$ і $K$ ( $1 \leq N \leq 100000$ 1 \leq N \leq 100000, $0 \leq K \leq 100$ 0 \leq K \leq 100), розділені пробілом. У наступних $N$ рядках знаходяться по два цілих числа $s_{i}$ s_i та $e_{i}$ e_i ( $0 \leq s_{i} \leq e_{i} \leq 1 0^{9}$ 0 \leq s_i \leq e_i \leq 10^9) — час початку та закінчення $i$ -ї лекції. Час вимірюється у хвилинах від моменту прибуття Арсенія. Усі вхідні числа — цілі.

Вихідні дані

Виведіть єдине число — максимальну кількість балів знань, яку Арсеній може отримати за день (день Арсенія не закінчується раніше завершення останньої лекції).

Приклади

Приклад 1