초도 관광

문제

JOI 군은 IOI 국에 있는 초도라는 도시의 관광 투어를 계획하게 되었다.

초도는 남북 방향으로 곧게 뻗은 W 개의 도로와, 동서 방향으로 곧게 뻗은 H 개의 도로에 의해 바둑판 모양으로 구획되어 있다.

남북 방향의 W 개의 도로에는 서쪽부터 순서대로 1, 2, ... , W 의 번호가 붙어 있다. 또한, 동서 방향의 H 개의 도로에는 남쪽부터 순서대로 1, 2, ... , H 의 번호가 붙어 있다. 서쪽에서 i 번째의 남북 방향 도로와, 남쪽에서 j 번째의 동서 방향 도로의 교차점을 (i, j) 로 나타낸다.

또한, 아래 그림과 같이, 각 교차점에서는 북동쪽으로 하나 떨어진 교차점으로 가는 길이 있다(가장 북쪽 도로 위의 교차점과 가장 동쪽 도로 위의 교차점은 제외). 또한, 남서쪽으로 하나 떨어진 교차점으로 가는 길도 있다(가장 남쪽 도로 위의 교차점과 가장 서쪽 도로 위의 교차점은 제외). 즉, 교차점 (i, j) 에서는, 만약 교차점 (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1) 이 있다면 그 교차점들로 길 1 개를 사용해 갈 수 있다. 그에 더해, 만약 교차점 (i - 1, j - 1), (i + 1, j + 1) 이 있다면 그 교차점들로도 길 1 개를 사용해 갈 수 있다.

JOI 군은 투어 계획으로서 이미 N 개의 관광 명소를 어떤 순서로 방문할지 정해 두었다. i 번째 (1 ≦ i ≦ N) 로 방문하는 관광 명소는 교차점 ($X_{i}$, $Y_{i}$) 에 있다. JOI 군은 투어에 걸리는 시간을 가능한 한 짧게 하기 위해, 지나야 하는 길의 개수를 적게 하고 싶다. 관광 명소를 미리 정한 순서로 방문하기 위해 지나야 하는 길의 개수의 합의 최솟값을 구하는 프로그램을 작성하시오.

단, 투어의 시작 지점은 교차점 ($X_{1}$, $Y_{1}$) 이다. 또한, 투어 도중에 초도의 밖으로 이동해서는 안 된다고 하자. 또한, JOI 군은 관광 명소가 있는 교차점을, 관광 명소를 방문하지 않고 통과할 수도 있다.

（예선 경기 실시 후 추가） 「길의 개수의 합」에 대한 보충. 투어 도중에 같은 길을 2 번 이상 지날 수도 있다. 그 경우, 「길의 개수의 합」으로는 그 길에 대해 지난 횟수만큼 중복해서 센다.

입력

입력은 1 + N 개의 줄로 이루어진다.

첫째 줄에는 공백으로 구분하여 3 개의 정수 W, H, N (2 ≦ W ≦ 10000, 2 ≦ H ≦ 10000, 1 ≦ N ≦ 1000) 이 주어진다.

이어지는 N 개의 줄 중 i 번째 줄 (1 ≦ i ≦ N) 에는 2 개의 정수 $X_{i}$, $Y_{i}$ (1 ≦ $X_{i}$ ≦ W, 1 ≦ $Y_{i}$ ≦ H) 이 공백으로 구분되어 주어진다. 이는 i 번째로 방문하는 관광 명소가 있는 교차점이 ($X_{i}$, $Y_{i}$) 임을 나타낸다.

출력

관광 명소를 순서대로 방문하기 위해 지나는 길의 개수의 합의 최솟값을 한 줄로 출력한다.

예제 입력 1

4 3 3
1 1
3 3
4 1

예제 출력 1

5

예제 1 에서는, 예를 들어 (1, 1), (2, 2), (3, 3), (3, 2), (4, 2), (4, 1) 의 순서로 교차점을 방문하면 된다.

예제 입력 2

4 3 5
1 3
4 3
2 2
2 2
1 3

예제 출력 2

7

예제 2 와 같이, 같은 교차점을 여러 번 방문할 수도 있다.