№689303674

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, - тёмной.

При анализе результатов эксперимента рассматривают линии. Линией называют группу светлых точек, расположенных в одном ряду подряд, то есть без тёмных точек между ними. Линия должна содержать не менее K светлых точек, слева и справа от линии должна быть тёмная точка или край

экрана. Вам необходимо по заданному протоколу определить наибольшее количество линий, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.

Входные данные представлены в файле следующим образом. В первой строке входного файла записано натуральное число N (1 ≤ N ≤ 100 000) - общее количество частиц, попавших на экран и натуральное число K (1 ≤ N ≤ 100 000) - минимальное число точек, образующих линию. Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер позиции в ряду.

Пример входного файла:

7 3

2 1

1 7

1 8

2 3

1 9

2 4

2 2

В данном случае существует две строки с номерами 1 и 2, которые содержат по одной линии длины 3 и 4 соответственно. Ответ: 1 2.