Treatment

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

One progressive pharmacy claims that burdock virus can be cured by drinking exactly \(k\) different correct pills.

From the product catalog of this pharmacy, it is known that it sells pills numbered with consecutive natural numbers starting from 1. Moreover, the pills are numbered in order of their price, and the \(i\)-th pill costs exactly \(i\) hryvnias. The pharmacy claims that pills with numbers from \(l_1\) to \(r_1\) (inclusive), from \(l_2\) to \(r_2\), \(\ldots\), with numbers from \(l_n\) to \(r_n\) cure the burdock virus.

Petro recently started having a runny nose, and he decided not to take risks and buy \(k\) different pills that cure the virus. Since Petro is a poor student, he wants to choose the \(k\) cheapest pills. Determine the minimum possible total cost of the purchased pills.

Input

The first line contains two integers \(n\) and \(k\) — the number of ranges of pill numbers that cure the virus, and the number of pills that need to be bought.

The next \(n\) lines contain pairs of numbers \(l_i\) and \(r_i\), one pair per line.

Note that the ranges may arbitrarily intersect or overlap.

Output

In a single line, print one integer — the answer to the problem.

If there are not \(k\) different pills that cure the virus — print -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

In the first test, the pills with the following numbers cure the virus: 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12. Among them, the 7 cheapest are 1, 2, 3, 4, 6, 7, and 8, so the answer is \(1+2+3+4+6+7+8 = 31\).

In the second test, there are only 4 pills that cure the virus. Therefore, the answer is -1.