BZPRO
#5102. [POI2018]Prawnicy
内存限制：128 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
定义一个区间(l,r)的长度为r-l，空区间的长度为0。
给定数轴上n个区间，请选择其中恰好k个区间，使得交集的长度最大。
输入格式
第一行包含两个正整数n,k(1<=k<=n<=1000000)，表示区间的数量。
接下来n行，每行两个正整数l,r(1<=l<r<=10^9)，依次表示每个区间。
输出格式
第一行输出一个整数，即最大长度。
第二行输出k个正整数，依次表示选择的是输入文件中的第几个区间。
若有多组最优解，输出任意一组。
样例
样例输入
6 3
3 8
4 12
2 6
1 10
5 9
11 12
样例输出
4
1 2 4
数据范围与提示
BZPRO