문제
서쪽의 노을을 바라보고 있는 꽃게 연준이가 광활한 모래밭의 한복판(1, 1)에서 자신의 집(M, N)까지 가려고 한다. 알다시피, 꽃게는 옆으로만 움직일 수 있기 때문에 처음에는 연준이가 남/북으로만 움직일 수 있다.
한편, 모래밭에는 K개의 돌림판이 있어서 돌림판 위에서는 연준이가 90도 회전할 수 있다. (정확히 90도씩만 회전할 수 있다.) 이 점을 이용해서 연준이는 돌림판을 잘 사용해서 날이 어둑어둑해지기 전에 빨리 집으로 가려고 한다.
연준이가 1만큼 움직이거나 90도 회전할 때 1의 시간이 걸린다고 할 때, 연준이가 집으로 갈 때 걸리는 최소 시간을 구하여라. 단, 동/서쪽으로 1만큼 움직이면 x좌표가 1/-1씩 증가하며, 남/북쪽으로 1만큼 움직이면 y좌표가 -1/1씩 증가한다.
입력
첫 번째 줄에는 연준이의 집의 좌표를 나타내는 자연수 M, N 과 돌림판의 수 K가 주어진다.
(1 ≤ M, N ≤ 100,000, 1 ≤ K ≤ 200,000)
두 번째 줄부터 K개의 줄에는 돌림판의 좌표 Xi, Yi (1 ≤ Xi ≤ M, 1 ≤ Yi ≤ N)가 주어진다.
전체 데이터의 20%는 M, N ≤ 1,000을 만족한다.
전체 데이터의 40%는 K ≤ 2,000을 만족한다.
전체 데이터의 60%는 위 조건 중 하나 이상을 만족한다.
출력
연준이가 자신의 집까지 갈 수 있는 최소 시간을 출력한다. 만약 연준이가 집까지 갈 수 없다면 -1을 출력한다.
예제1
입력
321
12
출력
4
예제2
입력
321
21
출력
-1
예제3
입력
8915
31
32
37
38
11
45
43
56
58
63
62
75
89
86
85
출력
26
힌트
출처
JOI 2012/2013 본선 3