“Byteasar & sons” 律师事务所接到了一项来自重要客户的紧急且艰巨的任务。该案件需要从事务所的 $n$ 名律师中选出 $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

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

输出格式 1

4
1 2 4

说明

样例说明：三名律师参加会议的最大持续时间为 $4$：会议从 $4$ 开始，到 $8$ 结束，可以由 1 号、2 号和 4 号律师参加。另一个同样好的方案是 2 号、4 号和 5 号律师参加，时间从 $5$ 到 $9$。

评分标准

测试集由以下子集组成。每个子集内可能包含多个测试点。如果你的程序在第一行输出了正确的数值，但后续输出错误，你将获得该测试点 $40\%$ 的分数。