Problem Statement

At yuki Inc., $N$ meetings are scheduled to be held. The $i$-th meeting starts at time $L_i$ and ends at time $R_i - 0.5$.

Shirotsume has decided to choose $K$ of the $N$ meetings and attend all of the chosen meetings. It is not allowed to join a meeting after it has started or to leave a meeting before it has ended, and it is not possible to attend $2$ or more different meetings at the same time.

Determine whether it is possible to choose the meetings so that all $K$ chosen meetings can be attended. If it is possible, let $L_x$ be the start time of the meeting with the earliest start time among the chosen meetings, and let $R_y - 0.5$ be the end time of the meeting with the latest end time among them. Find the minimum possible value of $R_y - L_x$.

Constraints

• All input values are integers
• $1 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq L_i \lt R_i \leq 10^9$

Input

The input is given from standard input. The test case is given in the following format.

$N$ $K$
$L_1$ $R_1$
$\vdots$
$L_N$ $R_N$

Output

If there is no way to choose $K$ meetings that can all be attended, print $-1$. Otherwise, print the minimum possible value of $R_y - L_x$. Under the constraints of this problem, this value is always an integer, so print it as an integer.

Sample

4 2
7 8
5 9
1 6
8 10

3

4 3
5 6
2 3
4 9
1 7

-1

10 4
525950013 820445834
981100444 993807420
36480556 467480126
785522823 927004654
495102449 874908810
418220824 550763124
900233408 954677357
229962778 551425731
239960064 429220203
827514759 843989743

467857407