{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"Многие программисты в Омске любят добираться до работы на метро — благо, головной офис расположен совсем недалеко от станции Проспект Рокоссовского. Ну а поскольку сидячий образ жизни требует активных физических нагрузок в свободное от работы время, многие сотрудники — в том числе и Никифор — ходят от дома до метро пешком.\n \u003cimg SRC\u003d\"CDN_BASE_URL/6526090360e64f6249b5e56cfac7a5ca?v\u003d1580482830\"\u003e \u003cbr\u003eНикифор живёт в таком районе нашего города, где улицы образуют правильную сетку кварталов; все кварталы являются квадратами с длиной стороны, равной 100 метрам. Вход на станцию метро расположен на одном из перекрёстков; Никифор начинает свой путь с другого перекрёстка, который расположен южнее и западнее входа в метро. Естественно, что выйдя из дома, Никифор всегда идет по улицам, ведущим либо на север, либо на восток. Некоторые кварталы, которые встречаются ему на пути, он может также пересечь по диагонали, ведущей из юго-западного угла квартала в северо-восточный. Таким образом, некоторые из маршрутов (ведущих всегда на север, восток или северо-восток), оказываются короче других. Никифора интересует, сколько времени понадобится ему на преодоление кратчайшего маршрута; для этого ему нужно знать его длину.\nВы должны написать программу, которая по имеющейся информации о виде сетки кварталов рассчитывает длину кратчайшего маршрута из юго-западного угла в северо-восточный.\n"}},{"title":"Ввод","value":{"format":"HTML","content":"В первой строке находятся два целых числа N и M (0 \u003c N, M ≤ 1000) — размер сетки кварталов с запада на восток и с юга на север соответственно. Никифор начинает путь с перекрёстка, который находится к юго-западу от квартала с координатами (1, 1); станция метро находится к северо-востоку от квартала с координатами (N, M). Во второй строке находится целое число K (0 ≤ K ≤ 100) — количество кварталов, через которые можно пройти наискось. Далее следуют K строк с парами целых положительных чисел, разделённых пробелами — координатами таких кварталов."}},{"title":"Вывод","value":{"format":"HTML","content":"Требуется вывести длину кратчайшего пути от дома Никифора до станции метро в метрах, округлённую до целых метров."}},{"title":"Example","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e TABLE.sample { border-collapse:collapse; border: solid 1px #1A5CC8; } TABLE.sample TR TD, TABLE.sample TR TH { border: solid 1px #1A5CC8; vertical-align: top; padding: 3px; } TABLE.sample TR TH { color: #1A5CC8; }\u003c/style\u003e\n \u003ctable class\u003d\"sample\"\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003cth width\u003d\"350\"\u003einput\u003c/th\u003e\n \u003cth width\u003d\"350\"\u003eoutput\u003c/th\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n3\n1 1\n3 2\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e383\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n "}}]}