题目描述

给定 $n$ 个区间，请从中挑出 $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$；