D. Отрезки отрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Little D — друг Little C, который очень любит интервалы вместо числа "$$$3$$$".

В данный момент у него есть $$$n$$$ отрезков на числовой оси, $$$i$$$-й из них — $$$[a_i,b_i]$$$.

Но только $$$n$$$ отрезков не могут его удовлевторить. Он определяет значение отрезка отрезков $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$, $$$l$$$ и $$$r$$$ целые) как длину объединения отрезков с номерами с $$$l$$$ по $$$r$$$.

Он хочет выбрать ровно $$$k$$$ различных отрезков отрезков, что сумма их значений максимальна. Помогите ему вычислить эту сумму.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq k \leq \text{min}\{\frac{n(n+1)}{2},10^9\}$$$) — количество отрезков у Little D и количество отрезков отрезков, которые он выберет.

Каждая из $$$n$$$ следующих строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$, $$$i$$$-я строка описывает $$$i$$$-й отрезок ($$$1 \leq a_i < b_i \leq 10^9$$$).

Выходные данные

Выведите единственное число — максимальную сумму значений, которую может получить Little D.

Примеры
Входные данные
2 1
1 3
2 4
Выходные данные
3
Входные данные
3 3
1 4
5 7
3 6
Выходные данные
15
Примечание

В первом примере Little D выберет $$$[1,2]$$$, объединение первого и второго отрезка это $$$[1,4]$$$, длина объединения — $$$3$$$.

Во втором примере Little D выберет $$$[1,2]$$$, $$$[2,3]$$$ и $$$[1,3]$$$, ответ будет равен $$$5+6+4=15$$$.