#P50236. 「NOI2016」区间

「NOI2016」区间

题目描述

在数轴上有 nn 个闭区间 [l1,r1],[l2,r2],...,[ln,rn][l_1,r_1],[l_2,r_2],...,[l_n,r_n]。现在要从中选出 mm 个区间,使得这 mm 个区间共同包含至少一个位置。换句话说,就是使得存在一个 xx,使得对于每一个被选中的区间 [li,ri][l_i,r_i],都有 lixril_i\leq x\leq r_i

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri][l_i,r_i] 的长度定义为 rilir_i−l_i,即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案,输出 1−1

输入格式

第一行包含两个正整数 n,mn,m 用空格隔开,意义如上文所述。保证 1mn1\leq m\leq n

接下来 nn 行,每行表示一个区间,包含用空格隔开的两个整数 lil_irir_i 为该区间的左右端点。

输出格式

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

样例

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

如图,当 n=6,m=3n=6,m=3 时,花费最小的方案是选取 [3,5][3,5][3,4][3,4][1,4][1,4] 这三个区间,他们共同包含了 44 这个位置,所以是合法的。其中最长的区间是 [1,4][1,4],最短的区间是 [3,4][3,4],所以它的花费是 (41)(43)=2(4−1)−(4−3)=2

数据范围与提示

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

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