시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 14 13 72.222%

문제

키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. 각각의 웅덩이는 (Ai, Bi)(|Ai| ≤ 500, |Bi| ≤ 500)에 위치해 있으며 키파는 눈이 좋아 이 웅덩이를 모두 볼 수 있다.

신아가 일찍 일어날 수도 있기 때문에 어서 (X, Y)에 있는 신아의 집에 최대한 빨리 도달해서 그녀가 잘 때 서프라이즈를 해 주고 싶지만, 장화가 새 것이기 때문에 웅덩이를 밟지 않는 것도 중요하다. 만일 키파가 상하좌우로만 이동할 수 있다면 웅덩이를 밟지 않으면서 신아에게 갈 수 있는 최소 거리는 얼마인가? 신아에게 가기 위해 웅덩이를 밟아야만 하는 경우는 없다고 가정한다.

입력

첫째 줄에 X, Y와 N이 공백을 사이에 두고 주어진다.

i+1 (1 ≤ i ≤ N) 번째 줄에 Ai와 Bi가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 키파가 웅덩이를 밟지 않고 신아에게 갈 수 있는 최소 거리를 출력하라.

예제 입력

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

예제 출력

11

힌트

신아는 (1, 2)에 있다. 키파는 예제 입력에서 주어진 7개의 웅덩이를 모두 볼 수 있다.

   4 . . . . . . . . 
   3 . M . . . . . . 
Y  2 . . M B M . M . 
   1 . M . M . M . . 
   0 . . * . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 
           X

가장 짧은 거리는 아래 그림에서 *로 표시된 길이다.

   4 ******* . . . . 
   3 * M . * . . . . 
Y  2 * . M B M . M . 
   1 * M . M . M . . 
   0 ***** . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 

           X