题目描述

题目译自 XXV Olimpiada Informatyczna — I etap Prawnicy

字节扎尔父子律师事务所刚接到一位重要客户的紧急委托。案子刻不容缓，需要从 $n$ 名律师中挑出 $k$ 人开会。每位律师都有一个连续的空闲时间段。你得选出 $k$ 名律师，让他们共同空闲的时间（即会议时间）尽可能长。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ $(1 \leq k \leq n)$，分别表示事务所的律师总数和需要开会的律师人数。

接下来的 $n$ 行，每行两个整数 $a_i$ 和 $b_i$ $(1 \leq a_i < b_i \leq 10^9)$，表示第 $i$ 名律师从时刻 $a_i$ 到 $b_i$ 空闲。

输出格式

第一行输出一个整数，表示会议的最长可能持续时间。可以假设会议时长至少为 $1$。

第二行输出 $k$ 个整数（空格分隔），表示参加会议的律师编号。律师的编号可以按任意顺序输出。若有多个正确答案，输出任意一个即可。

样例

输入

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

输出

4
1 2 4

三个律师的最长会议时间为 $4$。可选 $1$、$2$、$4$ 号律师，会议从时刻 $4$ 到 $8$。另一个合法的选择是 $2$、$4$、$5$ 号律师，会议从时刻 $5$ 到 $9$。

附加样例

• $n=7$, $k=3$，有两组律师可满足要求；
• $n=k=1000$, $a_i=i$, $b_i=10^6+i$；
• $n=1000$, $k=1$, $a_i=2i-1$, $b_i=2i$。

数据范围与提示

详细子任务附加限制及分值如下表所示。