9437 - Prawnicy

“Bajtazar 父子”律师事务所刚刚收到一位非常重要的客户的订单。案件严重、紧急,需要与律师事务所的律师举行会议。每个律师都有一段固定的空闲时间可以参加会议。你应该选择这样的 k 位律师,以便召开会议的时间(即他们都空闲的时间)尽可能长。

输入

第一行包含两个整数 nk\ (1\le k\le n),以一个空格隔开,表示事务所雇用的律师人数和召开会议所需的律师人数。

接下来 n 行,第 i 行包含两个整数 a_ib_i,(1\le a_i< b_i \le 10^9)
以一个空格隔开,表示第 i 个律师在时刻 a_i 和时刻 b_i 之间是空闲的。

输出

第一行输出一个整数,表示会议可能的最大时长。你可以假设你能够召开至少 1 人的会议。

第二行输出空格分隔的 k 个数,代表参加会议的律师编号(从 1 开始)。如果有多个正确答案,您的程序应输出其中任何一个。

样例

输入

6 3
3 8
4 12
2 6
1 10
5 9
11 12

输出

4
1 2 4

提示

样例解释

三位律师会议可能的最大时长是 4。编号为 124 的律师可以参加,持续时间从 48。另一个同样好的方案是让编号为 245 的律师参加,持续时间从 59

数据范围与提示 n\le 10^6

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题