Given $n$ closed intervals $[l_1, r_1], [l_2, r_2], …, [l_n, r_n]$, you need to choose $m$ intervals such that they have at least one common point. In other words, there exists a point $x$ such that for every chosen interval $[l_i, r_i]$, $l_i \leq x \leq r_i$.

For a satisfying selection, the cost of the choice is defined as the difference between the length of the longest interval and the length of the shortest interval. The length of an interval $[l_i, r_i]$ is defined as $r_i - l_i$.

Find the minimum cost possible, or if there is no valid selection, output -1.

Input

• The first line consists of two integers $n$ and $m$.
• The next $n$ lines, each containing two integers $l_i$ and $r_i$.

Output

• Output a single integer, the answer to the problem. If there is no valid selection, output -1.

Example

Input:

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

Output:

2

Explanation:

• Choose $3$ intervals $[3,5], [3,4], [1,4]$.

Constraints