26_0372

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

На специальный показ планируют пригласить семьи, в каждой из которых по L
человек. Администратор хочет разместить в одном ряду как можно больше семей.
Каждая семья должна занимать L свободных мест с последовательными номерами.
Места, занятые разными семьями, не должны пересекаться, при этом семьи могут
сидеть вплотную друг к другу.

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

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

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

Гарантируется, что в каждом ряду есть хотя бы одно забронированное место и
хотя бы в одном ряду можно разместить одну семью.

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

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

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

6 3 12 3
1 4
1 8
2 6
3 3
3 7
3 11

При таких исходных данных в рядах 1 и 2 можно разместить по три семьи, а в
ряду 3 — две семьи. Из двух подходящих рядов выбирается ряд с наибольшим
номером. Ответом является пара чисел 2 и 3.

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

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

• 26_0372.txt