問題文

yuki 株式会社では、 これから $N$ 個のミーティングが開催される予定です。 $i$ 個目のミーティングは時刻 $L_i$ に開始し、時刻 $R_i - 0.5$ に終了します。

Shirotsume くんは $N$ 個のミーティングから $K$ 個を選び、選んだミーティングすべてに出席することにしました。ミーティングは途中参加、途中退出はできず、同じ時刻に $2$ つ以上の異なるミーティングに出席することはできません。

選んだ $K$ 個のミーティングすべてに出席できるような選び方が可能であるか判定してください。可能であれば、選んだミーティングのうち開始時刻が最も早いものの開始時刻を $L_x$ 、終了時刻が最も遅いものの終了時刻を $R_y - 0.5$ としたとき、$R_y - L_x$ の値として考えられる最小値を求めてください。

制約

• 入力はすべて整数
• $1 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq L_i \lt R_i \leq 10^9$

入力

入力は標準入力から与えられる。テストケースは以下の形式で与えられる。

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

出力

$K$ 個のミーティングに出席できるような選び方が存在しないなら $-1$ を出力せよ。存在するなら、 $R_y - L_x$ の値として考えられる最小値を出力せよ。この問題の制約下でこの値は必ず整数となるので、整数として出力すること。

サンプル

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