题目描述

题目译自 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$。

附加样例

1. $n=7, k=3$，有两组律师可满足要求；
2. $n=k=1000, a_{i}=i, b_{i}=10^{6}+i$；
3. $n=1000, k=1, a_{i}=2i-1, b_{i}=2i$。

数据范围与提示

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