题目背景

题目译自 POI XXV - I etap 「Prawnicy」

题目描述

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

简要题意

输入格式

第一行包含两个整数 $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$ 开始）。如果有多个正确答案，您的程序应输出其中任何一个。

输入输出样例 #1

输入 #1

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

输出 #1

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\%$ 的分数。