题目描述

在数轴上有 $n$ 个闭区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$。现在要从中选出 $m$ 个区间，使得这 $m$ 个区间共同包含至少一个位置。换句话说，就是存在一个 $x$，使得对于每一个被选中的区间 $[l_i, r_i]$，都有 $l_i \leq x \leq r_i$。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 $[l_i, r_i]$ 的长度定义为 $r_i - l_i$,即等于它的右端点的值减去左端点的值.

求所有合法方案中最小的花费。如果不存在合法的方案，输出 $-1$。

输入格式

第一行包含两个正整数 $n, m$，用空格隔开，保证 $1 \leq m \leq n$。
接下来 $n$ 行，每行表示一个区间，包含用空格隔开的两个整数 $l_i$ 和 $r_i$。

输出格式

只有一行，包含一个正整数，即最小花费。

样例

输入：

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

输出：

2

如图，当 $n=6$,$m=3$ 时,花费最小的方案是选取 $[3,5]$、$[3,4]$、$[1,4]$ 这三个区间，它们共同包含 $4$ 这个位置,所以是合法的。 其中最长的区间是 $[1,4]$ ，最短的区间是 $[3,4]$ ，所以它的花费为 $(4−1)−(4−3)=2$。

数据范围与提示

所有测试数据的范围和特点如下表所示：