A91994.「NOI2016」区间

在数轴上有 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],...,[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$ 为该区间的左右端点。

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

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

测试点编号	$ n $	$ m $	$ l_i,r_i $
1	$ 20 $	$ 9 $	$ 0 \le l_i \le r_i \le 100 $
2	$ 20 $	$ 10 $	$ 0 \le l_i \le r_i \le 100 $
3	$ 199 $	$ 3 $	$ 0 \le l_i \le r_i \le 100000 $
4	$ 200 $	$ 3 $	$ 0 \le l_i \le r_i \le 100000 $
5	$ 1000 $	$ 2 $	$ 0 \le l_i \le r_i \le 100000 $
6	$ 2000 $	$ 2 $	$ 0 \le l_i \le r_i \le 100000 $
7	$ 199 $	$ 60 $	$ 0 \le l_i \le r_i \le 5000 $
8	$ 200 $	$ 50 $	$ 0 \le l_i \le r_i \le 5000 $
9	$ 200 $	$ 50 $	$ 0 \le l_i \le r_i \le 10^9 $
10	$ 1999 $	$ 500 $	$ 0 \le l_i \le r_i \le 5000 $
11	$ 2000 $	$ 400 $	$ 0 \le l_i \le r_i \le 5000 $
12	$ 2000 $	$ 500 $	$ 0 \le l_i \le r_i \le 10^9 $
13	$ 30000 $	$ 2000 $	$ 0 \le l_i \le r_i \le 100000 $
14	$ 40000 $	$ 1000 $	$ 0 \le l_i \le r_i \le 100000 $
15	$ 50000 $	$ 15000 $	$ 0 \le l_i \le r_i \le 100000 $
16	$ 100000 $	$ 20000 $	$ 0 \le l_i \le r_i \le 100000 $
17	$ 200000 $	$ 20000 $	$ 0 \le l_i \le r_i \le 10^9 $
18	$ 300000 $	$ 50000 $	$ 0 \le l_i \le r_i \le 10^9 $
19	$ 400000 $	$ 90000 $	$ 0 \le l_i \le r_i \le 10^9 $
20	$ 500000 $	$ 200000 $	$ 0 \le l_i \le r_i \le 10^9 $