3765: 区间交集
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：1
题目描述
给定 $n$ 个区间，请从中挑出 $k$ 个区间，使得它们的**交集**长度到达最大。区间的长度定义为这个区间的右端点与左端点的差。
所谓 $k$ 个区间的交集，是指这些区间共有的部分。
输入
第一行：两个整数 $n$ 与 $k$；
接下来 $n$ 行：每行两个整数 $a_i$ 与 $b_i$，表示一个区间的左端点与右端点。
输出
单个整数：表示**交集**的最大长度。
样例输入 复制
5 2
1 10
5 7
3 6
4 8
2 9样例输出 复制
7提示
+ 对于 $30\%$ 的数据，$1\leq k\leq n\leq 20$；
+ 对于 $60\%$ 的数据，$1\leq k\leq n\leq 2000$；
+ 对于 $100\%$ 的数据，$1\leq k\leq n\leq 100000$；
+ $1\leq a_i\leq b_i\leq 500000$；