Лікування

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.