1201. Петя участвует в расширенной версии игры «Морской бой» (5)
Петя участвует в расширенной версии игры «Морской бой». В данной версии игры,
в отличие от классической, допускается увеличение количества и длины кораблей,
а игровое поле может быть прямоугольным, размером М К, где М - количество
горизонтальных рядов клеток на игровом поле (целое положительное число,
не превышающее 100 000), К - количество вертикальных рядов клеток на игровом
поле (целое положительное число, не превышающее 100 000). Нумерация
горизонтальных рядов поля идёт сверху вниз с 1, а вертикальных - слева направо
также с 1. Некоторые клетки поля уже заняты кораблями (п-палубный корабль
занимает, соответственно, и подряд идущих клеток).
Пете необходимо разместить 2-палубный корабль, расположив его на свободных
клетках некоторого одного ряда так, чтобы корабль находился как можно дальше
от верхнего края игрового поля и все клетки игрового поля, находящиеся
непосредственно над ним, не были заняты другими кораблями. Допускается ставить
корабли вплотную друг к другу.
Если в найденном для размещения корабля ряду мест, удовлетворяющих условию,
несколько, то найдите место с наименьшими номерами вертикальных рядов.
Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля
есть.
Входные данные.
В первой строке входного файла находятся три числа: N - количество клеток
игрового поля, в которых расположены однопалубные корабли или части
многопалубных кораблей (N - целое положительное число, не превышающее 100 000),
М - количество горизонтальных рядов игрового поля и К - количество вертикальных
рядов игрового поля. В следующих № строках соответственно находятся пары
натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового
поля, в которых расположены корабли или их части (первое число не превышает
значения М, а второе - K).
Запишите в ответе два целых числа: номер горизонтального ряда и наименьший
из двух номеров вертикальных рядов, где необходимо разместить корабль.
