Лікування

Обмеження: 2 сек., 256 МіБ

Одна прогресивна аптека стверджує, що реп’яховірус можна вилікувати, якщо випити рівно \(k\) різних правильних таблеток.

Із каталогу продуктів цієї аптеки відомо, що вона продає таблетки, які пронумеровані послідовними натуральними числами починаючи від 1. Більше того, таблетки пронумеровані за зростанням їхньої ціни, причому \(i\)-та таблетка коштує рівно \(i\) гривень. Аптека стверджує, що таблетки із номерами від \(l_1\) до \(r_1\) (включно), із номерами від \(l_2\) до \(r_2\), \(\ldots\), із номерами від \(l_n\) до \(r_n\) лікують реп’яховірус.

У Петра недавно почався нежить, і він вирішив не ризикувати та купити \(k\) різних таблеток, які лікують вірус. Оскільки Петро бідний студент, він хоче обрати \(k\) найдешевших таблеток. Визначте, якою є мінімально можлива сумарна вартість придбаних таблеток.

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(k\) — кількість проміжків номерів таблеток, які лікують вірус, а також кількість таблеток, які потрібно купити.

У наступних \(n\) рядках задано пари чисел \(l_i\) та \(r_i\), по одній парі у рядку.

Зауважте, що проміжки можуть довільним чином перетинатись або накладатись.

Вихідні дані

У єдиному рядку виведіть одне ціле число — відповідь на задачу.

Якщо немає \(k\) різних таблеток, які лікують вірус — виведіть -1.

Обмеження

\(1 \le n \le 100\),

\(1 \le k \le 10^9\),

\(1 \le l_i \le r_i \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 7 1 2 2 4 6 12	31

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 5 4 7	-1

Примітки

У першому тесті таблетки з наступними номерами лікують вірус: 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12. Серед них найдешевшими 7-ма є 1, 2, 3, 4, 6, 7 та 8, отже відповідь — \(1+2+3+4+6+7+8 = 31\).

У другому тесті є лише 4 таблетки, які лікують вірус. Отже, відповідь -1.