26_0371

В концертном зале находятся M рядов, в каждом из которых имеется K мест.
Ряды пронумерованы от сцены начиная с 1, места в каждом ряду также
пронумерованы начиная с 1. Известно, какие места уже заняты зрителями.

Для проведения телевизионной съёмки требуется установить площадку, которая
занимает L мест с последовательными номерами в одном ряду. Поскольку площадка
может мешать зрителям, все места с теми же номерами в рядах, расположенных
дальше от сцены, должны быть свободны. Места, на которых устанавливается
площадка, также должны быть свободны.

Определите наименьший номер ряда, в котором можно установить площадку, и
количество различных вариантов её размещения в найденном ряду. Два варианта
считаются различными, если у них различаются номера первых мест. Варианты могут
пересекаться.

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

В первой строке входного файла находятся четыре натуральных числа: N —
количество занятых мест (N ≤ 100 000), M — количество рядов (M ≤ 100 000),
K — количество мест в каждом ряду (K ≤ 100 000) и L — количество мест,
занимаемых площадкой (2 ≤ L ≤ K). В следующих N строках находятся пары
натуральных чисел: номер ряда и номер занятого места соответственно.

Гарантируется, что существует хотя бы один вариант размещения площадки.

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

Запишите два целых числа: сначала наименьший номер ряда, затем количество
вариантов размещения площадки в этом ряду.

Типовой пример организации данных во входном файле

8 7 8 3
2 1
4 2
4 3
1 4
3 5
2 6
1 7
6 8

При таких исходных данных площадку можно установить в ряду 4 на местах с
номерами 4, 5, 6 или на местах с номерами 5, 6, 7. В рядах с меньшими номерами
подходящих вариантов нет. Ответом является пара чисел 4 и 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания
используйте данные из прилагаемого файла.

Файлы к заданию:

• 26_0371.txt