Лікування

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

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

Output

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

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

Constraints

$1 \le n \le 100$,

$1 \le k \le 10^9$,

$1 \le l_i \le r_i \le 10^9$.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 7 1 2 2 4 6 12	31

Input (stdin) сopy	Output (stdout) сopy
1 5 4 7	-1

Notes

У першому тесті таблетки з наступними номерами лікують вірус: 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.