Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Пираты!

В настолькой игре "Пираты!" задача одного из игроков состоит в том, чтобы провести торговый корабль с ценным грузом через море, на островах которого базируются пираты.
Поле представляют собой прямоугольник, состоящий из квадратных клеток. Игрок может за один ход перейти в одну из четырех соседних по стороне клеток, не выходя при этом за пределы поля. Торговый корабль начинает свой путь в любой клетке самого левого столбца и должен попасть в любую клетку самого правого столбца игрового поля.
Пиратские базы расположены на островах, которые также занимают одну клетку игрового поля, их расположение известно.
Вася выяснил, что чем больше расстояние от пиратской базы, тем безопаснее маршрут. расстояние считается как количество ходов по клеткам от пиратских баз до каждой из клеток маршрута.
Помогите ему определить, на какое минимальное расстояние придјтся подойти к пиратской базе, двигаясь по самому безопасному маршруту.

Формат входных данных
В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000)  количество строк и столбцов на игровом поле.
Во второй строке записано натуральное число K (1 <= K <= 500)  количество пиратских баз.
В следующих K строках записаны пары чисел Ri , Ci (1 <= Ri <= N, 1 <= Ci <= M)  координаты пиратских баз (строка, столбец).

Формат выходных данных
Выведите одно число  минимальное расстояние, на которое придется приближаться к пиратской базе на самом безопасном маршруте.
Система оценки
Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод Вывод
10 10
4
2 2
5 3
5 9
8 8
3

Замечание
Пример одного из безопасных маршрутов показан на рисун ке. Пиратские базы обозначены чјрным, клетки маршрута серым. Минимальное расстояние от пиратской базы до маршрута 3 хода.


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: