[NOI2016]区间

题目描述

在数轴上有 $N$ 个闭区间 $[l_1,r_1],[l_2,r_2],...,[l_n,r_n]$ 。现在要从中选出 $M$ 个区间,使得这 $M$ 个区间共同包含至少一个位置。换句话说,就是使得存在一个 $x$ ,使得对于每一个被选中的区间$[l_i,r_i]$ ,都有 $l_i≤x≤r_i$ 。 对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间$[l_i,r_i]$ 的长度定义为$r_i-l_i$ ,即等于它的右端点的值减去左端点的值。 求所有合法方案中最小的花费。如果不存在合法的方案,输出 $-1$ 。

输入输出格式

输入格式


第一行包含两个正整数 $N,M$ 用空格隔开,意义如上文所述。保证 $1 \leq M \leq N$。 接下来 $N$ 行,每行表示一个区间,包含用空格隔开的两个整数 $l_i$ 和 $r_i$ 为该区间的左右端点。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

![](https://cdn.luogu.com.cn/upload/pic/2390.png) ### 数据范围 | 测试点编号 | $ 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 $ |