26_0285

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

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

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

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

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

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

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

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

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

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

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

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

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

• 26_0285.txt