There are $n$ closed intervals $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$ on the number line. You need to select $m$ intervals from these such that these $m$ intervals share at least one common position. In other words, there must exist an $x$ such that for every selected interval $[l_i, r_i]$, we have $l_i \le x \le r_i$.

For a valid selection, the cost is defined as the length of the longest selected interval minus the length of the shortest selected interval. The length of an interval $[l_i, r_i]$ is defined as $r_i - l_i$, which is the value of its right endpoint minus the value of its left endpoint.

Find the minimum cost among all valid selection schemes. If no valid scheme exists, output $-1$.

Input

The first line contains two positive integers $n$ and $m$, separated by a space, as described above. It is guaranteed that $1 \le m \le n$.

The next $n$ lines each represent an interval, containing two integers $l_i$ and $r_i$ separated by a space, representing the left and right endpoints of the interval.

Output

Output a single line containing a single integer, the minimum cost.

Examples

Input 1

6 3
3 5
1 2
3 4
2 2
1 5
1 4

Output 1

2

Note

As shown in the figure, when $n = 6$ and $m = 3$, the scheme with the minimum cost is to select the three intervals $[3, 5]$, $[3, 4]$, and $[1, 4]$. They all contain the position $4$, so it is valid. The longest interval is $[1, 4]$ and the shortest is $[3, 4]$, so the cost is $(4 - 1) - (4 - 3) = 2$.

Input 2

See interval/interval2.in in the contestant directory.

Output 2

See interval/interval2.ans in the contestant directory.

Input 3

See interval/interval3.in in the contestant directory.

Output 3

See interval/interval3.ans in the contestant directory.

Subtasks

The ranges and characteristics of all test data are shown in the table below: