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