26_0308

Задание выполняется с использованием прилагаемых файлов.

Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером $M \times K$, где $M$ — количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$), $K$ — количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$). Нумерация горизонтальных рядов поля идёт сверху вниз с $1$, а вертикальных — слева направо также с $1$. Некоторые клетки поля уже заняты кораблями ($n$-палубный корабль занимает, соответственно, $n$ подряд идущих клеток).

Пете необходимо разместить 1-палубный корабль, расположив его на свободной клетке игрового поля так, чтобы до ближайшего по направлению вверх препятствия (корабля, части многопалубного корабля или края игрового поля) было как можно больше свободных клеток. Допускается ставить корабли вплотную друг к другу.

Если горизонтальных рядов для удовлетворяющего условию размещения корабля несколько, то необходимо указать горизонтальный ряд с наименьшим номером. Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.

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

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

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

Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.

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

• 26_0308.txt