변호사

법률 사무소 '바이타자르와 아들들'에 매우 중요한 고객으로부터 긴급한 사건이 들어왔다. 사안이 급해서 사무소에 고용된 $n$명의 변호사 중 $k$명이 회의를 열어야 한다. 각 변호사에게는 다른 일정이 없는 연속된 자유 시간이 하나씩 있다. 모든 $k$명이 동시에 자유로운 시간이 최대한 길어지도록 $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$개를 공백으로 구분해 출력한다. 정답이 여러 개이면 그중 아무거나 출력해도 된다.

$n \le 1\,000\,000$

변호사 3명으로 열 수 있는 가장 긴 회의의 길이는 4이다. 1번, 2번, 4번 변호사가 참석할 수 있으며, 이 회의는 시각 4부터 시각 8까지 진행된다. 2번, 4번, 5번 변호사도 똑같이 좋은 선택이며, 시각 5부터 시각 9까지 진행된다.