题目描述
在数轴上有 n 个闭区间从 1 至 n 编号,第 i 个闭区间为 [li,ri] 。
现在要从中选出 m 个区间,使得这 m 个区间共同包含至少一个位置。换句话说,就是使得存在一个 x ,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri 。
对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。
区间 [li,ri] 的长度定义为 (ri−li) ,即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。
输入格式
第一行包含两个整数,分别代表 n 和 m。
第 2 到第 (n+1) 行,每行两个整数表示一个区间,第 (i+1) 行的整数 li,ri 分别代表第 i 个区间的左右端点。
输出格式
输出一行一个整数表示答案。
6 3
3 5
1 2
3 4
2 2
1 5
1 4
2
提示
样例输入输出 1 解释
如图,当 n=6,m=3 时,花费最小的方案是选取 [3,5],[3,4],[1,4] 这三个区间,它们共同包含了 4 这个位置,所以是合法的。其中最长的区间是 [1,4],最短的区间是 [3,4],所以它的花费是 (4−1)−(4−3)=2。
数据规模与约定
本题共 20 个测试点,各测试点信息如下表。
| 测试点编号 | n= | m= | li,ri |
|:-:|:-:|:-:|:-:|
| 1 | 20 | 9 | 0≤li≤ri≤100 |
| 2 | 20 | 10 | 0≤li≤ri≤100 |
| 3 | 199 | 3 | 0≤li≤ri≤100000 |
| 4 | 200 | 3 | 0≤li≤ri≤100000 |
| 5 | 1000 | 2 | 0≤li≤ri≤100000 |
| 6 | 2000 | 2 | 0≤li≤ri≤100000 |
| 7 | 199 | 60 | 0≤li≤ri≤5000 |
| 8 | 200 | 50 | 0≤li≤ri≤5000 |
| 9 | 200 | 50 | 0≤li≤ri≤109 |
| 10 | 1999 | 500 | 0≤li≤ri≤5000 |
| 11 | 2000 | 400 | 0≤li≤ri≤5000 |
| 12 | 2000 | 500 | 0≤li≤ri≤109 |
| 13 | 30000 | 2000 | 0≤li≤ri≤100000 |
| 14 | 40000 | 1000 | 0≤li≤ri≤100000 |
| 15 | 50000 | 15000 | 0≤li≤ri≤100000 |
| 16 | 100000 | 20000 | 0≤li≤ri≤100000 |
| 17 | 200000 | 20000 | 0≤li≤ri≤109 |
| 18 | 300000 | 50000 | 0≤li≤ri≤109 |
| 19 | 400000 | 90000 | 0≤li≤ri≤109 |
| 20 | 500000 | 200000 | 0≤li≤ri≤109 |
对于全部的测试点,保证 1≤m≤n,1≤n≤5×105,1≤m≤2×105,0≤li≤ri≤109。