Задание №26

При бронировании билетов на теплоход известно, какие каюты на жилой палубе уже заняты. Палуба представима в виде сетки из M рядов, каждый из которых содержит K кают. Необходимо забронировать две соседние каюты в таком ряду, чтобы в нём было забронировано не менее 35 кают, а в двух соседних рядах (сзади и спереди) было как можно больше свободных кают, причём крайние ряды для брони рассматривать не следует. Если существует несколько вариантов бронирования, удовлетворяющих этим условиям, следует выбрать ряд с наибольшим номером.

В ответе запишите два целых числа: искомый номер ряда и суммарное количество забронированных кают в соседних (относительно выбранных мест) рядах. Нумерация рядов и кают ведётся с 1. Гарантируется, что бронь, соответствующая условиям, возможна.

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

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

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

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

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

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

При таких исходных данных и отсутствии ограничений на количество забронированных в ряду кают ответом является пара чисел 6 и 1.