D. Федор и купоны
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все наши герои имеют хобби. И Федор не исключение. Ему очень нравится ходить в супермаркет около дома и покупать всякие вещи.

Все товары в супермаркете имеют уникальный целый номер. И для каждого уникального целого номера найдется ровно один товар в супермаркете. Так как Федор делает много покупок, ему хотелось бы посещать супермаркет с экономией. Поэтому у него есть n скидочных купонов. i-й купон действует на товарах с номерами с li-го по ri-й включительно. Сегодня он решил взять с собой в супермаркет ровно k купонов.

Федор хочет выбрать k купонов так, чтобы количество таких товаров x, что на товар x действуют все купоны, было максимально (для лучшего понимания посмотрите примеры). Федор, кроме денег, ещё хочет сэкономить силы и время, поэтому просит вас сделать выбор купонов. Помогите Федору!

Входные данные

В первой строке входных данных находятся два целых числа n, k (1 ≤ k ≤ n ≤ 3·105) — количество купонов у Федора и количество купонов, которые следует выбрать.

В каждой из следующих n строк входных данных находятся два целых числа li и ri ( - 109 ≤ li ≤ ri ≤ 109) — описание i-го купона. Купоны могут совпадать.

Выходные данные

В первой строке следует вывести единственное целое число — максимальное количество товаров, на которые действуют все купоны. То есть товар, на который не действует какой-то из выбранных купонов, не считается.

В следующей строке выходных данных следует вывести k различных целых чисел p1, p2, ..., pk (1 ≤ pi ≤ n) — номера купонов, выбрав которые, мы получим максимальное количество товаров, на которые действуют все эти купоны.

Если оптимальных ответов несколько, выведите любой.

Примеры
Входные данные
4 2
1 100
40 70
120 130
125 180
Выходные данные
31
1 2
Входные данные
3 2
1 12
15 20
25 30
Выходные данные
0
1 2
Входные данные
5 2
1 10
5 15
14 50
30 70
99 100
Выходные данные
21
3 4
Примечание

В первом примере, если Федор возьмет первые два купона, то они оба будут действовать на все товары в отрезке [40, 70]. Всего таких товаров 31.

Во втором примере ни на один товар не действуют два купона, поэтому ответ 0. Федор может взять любые два купона в этом примере.