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\) различных отрезков отрезков, что сумма их значений максимальна. Помогите ему вычислить эту сумму.
Выходные данные
Выведите единственное число — максимальную сумму значений, которую может получить Little D.
Примечание
В первом примере Little D выберет \([1,2]\), объединение первого и второго отрезка это \([1,4]\), длина объединения — \(3\).
Во втором примере Little D выберет \([1,2]\), \([2,3]\) и \([1,3]\), ответ будет равен \(5+6+4=15\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 3
2 4
|
3
|
|
2
|
3 3
1 4
5 7
3 6
|
15
|