При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.
При анализе результатов эксперимента рассматривают линии. Линией называют группу светлых точек, расположенных в одном ряду подряд, то есть без тёмных точек между ними. Линия должна содержать не менее K светлых точек, слева и справа от линии должна быть тёмная точка или край
экрана. Вам необходимо по заданному протоколу определить наибольшее количество линий, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные представлены в файле 26-104.txt следующим образом. В первой строке входного файла записано натуральное число 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.