서쪽의 노을을 바라보고 있는 꽃게 연준이가 광활한 모래밭의 한복판(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을 출력한다.

3 2 1
1 2

4

3 2 1
2 1

-1

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

26

연준이는 다음과 같은 방법으로 움직이면 최소 시간으로 집까지 갈 수 있다. 1) 연준이가 (1,1)에서 90도 회전한 후 (3,1)까지 움직인다. 2) 연준이가 (3,1)에서 90도 회전한 후 (3,8)까지 움직인다. 3) 연준이가 (3,8)에서 90도 회전한 후 (5,8)까지 움직인다. 4) 연준이가 (5,8)에서 90도 회전한 후 (5,6)까지 움직인다. 5) 연준이가 (5,6)에서 90도 회전한 후 (8,6)까지 움직인다. 6) 연준이가 (8,6)에서 90도 회전한 후 (8,9)까지 움직인다.