[POI2018] Prawnicy

**题目译自 [POI XXV - I etap](https://sio2.mimuw.edu.pl/c/oi25-1/dashboard/) 「[Prawnicy](https://sio2.mimuw.edu.pl/c/oi25-1/p/pra/)」**

“Bajtazar 父子”律师事务所刚刚收到一位非常重要的客户的订单。案件严重、紧急，需要与律师事务所的律师举行会议。每个律师都有一段固定的空闲时间可以参加会议。你应该选择这样的 $k$ 位律师，以便召开会议的时间（即他们都空闲的时间）尽可能长。 [简要题意](https://www.luogu.com.cn/problem/U252799)

第一行包含两个整数 $n$ 和 $k\ (1\le k\le n)$，以一个空格隔开，表示事务所雇用的律师人数和召开会议所需的律师人数。 接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_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$。编号为 $1$、$2$ 和 $4$ 的律师可以参加，持续时间从 $4$ 到 $8$。另一个同样好的方案是让编号为 $2$、$4$ 和 $5$ 的律师参加，持续时间从 $5$ 到 $9$。  #### 附加样例 参见 `pra/pra*.in` 和 `pra/pra*.out`： - 附加样例 $1$：$1$ 组数据，$n=7$，$k=3$，且选择律师的方案有两种。 - 附加样例 $2$：$1$ 组数据，$n=k=1000$，$a_i=i$，$b_i=10^6+i$； - 附加样例 $3$：$1$ 组数据，$n=1000$，$k=1$，$a_i=2i-1$，$b_i=2i$； #### 数据范围与提示 测试集分为以下子任务。每个子任务的测试由一个或多个单独的测试组组成。 | Subtask # | 额外限制 | 分值 | |:---------:|:----------------------------:|:---:| | $1$ | $n\le 20$ | $20$ | | $2$ | $n\le 300$，$a_i,b_i\le 300$ | $15$ | | $3$ | $n\le 5000$ | $15$ | | $4$ | $n\le 10^6$，$k\in \{1,n\}$ | $15$ | | $5$ | $n\le 10^6$ | $35$ | 如果你的程序在第一行输出了正确的时长，但其余的输出是错误的，那么你将获得 $40\%$ 的分数。