题目描述

数轴上有 $N$ 块布。第 $i$ 块布 $(1 \le i \le N)$ 覆盖数轴上的闭区间 $[L_i, R_i]$。数轴上的一个点可能被两块以上的布覆盖，也可能一块布都没盖到。

两块布「重叠」：指存在数轴上的某个点，同时被这两块布覆盖。

对于不重叠的两块布，定义它们的距离为：

• 在一块布覆盖的点 $p$ 与另一块布覆盖的点 $q$ 中，$|p - q|$ 的最小值。

对于两两互不重叠的 $K$ 块布，定义它们的得分为这些布两两之间距离的最小值。

请从 $N$ 块布中选出两两互不重叠的 $K$ 块，求得分的最大值。

如果无法选出这样的 $K$ 块布，输出 -1。

输入格式

N K
L_1 R_1
L_2 R_2
...
L_N R_N

输出格式

输出一个整数表示答案；若无解则输出 -1。

输入示例 1

6 3
1 12
2 7
5 9
9 13
10 18
15 20

输出示例 1

2

示例 1 说明

选第 $2$、第 $4$、第 $6$ 块布，即区间 $[2,7]$、$[9,13]$、$[15,20]$，它们两两互不重叠。

• 第 $2$ 块与第 $4$ 块的距离为 $9 - 7 = 2$；
• 第 $2$ 块与第 $6$ 块的距离为 $15 - 7 = 8$；
• 第 $4$ 块与第 $6$ 块的距离为 $15 - 13 = 2$。

得分是三者的最小值 $2$。因为找不到得分 $\ge 3$ 的选法，所以答案是 $2$。

输入示例 2

2 2
1 5
5 9

输出示例 2

-1

示例 2 说明

请注意：第 $1$ 块布 $[1,5]$ 与第 $2$ 块布 $[5,9]$ 只在 $5$ 这一个点上相交，但这也算重叠。 只有这两块布可选，却互相重叠，因此无法选出两块互不重叠的布，输出 -1。

输入示例 3

20 5
169 748
329 586
529 972
432 520
408 587
138 250
114 656
299 632
755 984
404 772
155 506
832 854
353 465
374 387
384 567
555 631
428 951
104 705
405 530
102 258

输出示例 3

35

示例 3 说明

在这 $20$ 块布中，能选出两两互不重叠的 $5$ 块，且相邻两块之间的距离都不小于 $35$；但要做到都不小于 $36$ 就不可能了，所以答案是 $35$。

约束条件

• $2 \le K \le N \le 2 \times 10^5$
• $0 \le L_i < R_i \le 10^9 \ (1 \le i \le N)$
• 所有输入值均为整数