Language:

English
Russian

Практикум по программированию

Для участников:
Регистрация  ||   Вход
Список соревнований
Вы не вошли в систему! Вход или регистрация.

Кратчайший путь

Time limit:1 sec.
Memory limit: 1048576 KByte

Студент Василий живёт в городе, где улицы образуют правильную сетку кварталов: все кварталы являются квадратами с длиной стороны, равной 100 метрам. Дом Василия располагается в юго-западном углу – точке с координатами (0, 0). Университет располагается в северо-восточном углу – точке с координатами (N, M).

Выйдя утром из дома, Василий идёт в университет. Он движется по улицам, но при этом некоторые кварталы может пересечь также по диагонали, ведущей из юго-западного угла квартала в северо-восточный.

Напишите программу, которая вычислит длину кратчайшего маршрута от дома до университета.

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

В первой строке находятся два целых числа N и M (0 < N, M ≤ 109) – размер сетки кварталов с запада на восток (по горизонтали) и с юга на север (по вертикали) соответственно.

Во второй строке находится целое число K (0 ≤ K ≤ 105) – количество кварталов, через которые можно пройти наискосок.

Далее следуют K строк с парами целых положительных чисел x и y, разделённых пробелами – координаты северо-восточных углов таких кварталов (1 ≤ x ≤ N, 1 ≤ y ≤ M).

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

Требуется вывести длину кратчайшего пути от дома Василия до университета в метрах, округлённую до ближайшего целого.

Пример

Входные данные
3 2
3
1 1
3 2
1 2
Выходные данные
383

Условия всех задач турнира (pdf)

© Copyright ВоГУ, АВТ, Носов Д.А., Смоленцев К.Н.