JOI 군은 IOI 나라에 있는 초도라는 도시의 관광 여행을 짜게 되었다.

초도는 남북으로 곧게 뻗은 도로 \(W\)개와 동서로 곧게 뻗은 도로 \(H\)개로 바둑판처럼 나뉘어 있다. 남북 도로에는 서쪽부터 \(1, 2, \ldots, W\)번이, 동서 도로에는 남쪽부터 \(1, 2, \ldots, H\)번이 붙어 있다. 서쪽에서 \(i\)번째 남북 도로와 남쪽에서 \(j\)번째 동서 도로의 교차로를 \((i, j)\)로 나타낸다.

각 교차로에서는 북동쪽 한 칸 교차로로 가는 길이 있다(가장 북쪽 도로 위의 교차로와 가장 동쪽 도로 위의 교차로는 제외). 또 남서쪽 한 칸 교차로로 가는 길도 있다(가장 남쪽 도로 위의 교차로와 가장 서쪽 도로 위의 교차로는 제외). 곧, 교차로 \((i, j)\)에서는 교차로 \((i-1, j)\), \((i+1, j)\), \((i, j-1)\), \((i, j+1)\)이 있으면 그곳으로 길 하나로 갈 수 있다. 여기에 더해 교차로 \((i-1, j-1)\), \((i+1, j+1)\)이 있으면 그곳으로도 길 하나로 갈 수 있다.

JOI 군은 이미 관광 명소 \(N\)곳을 어떤 순서로 돌지 정해 두었다. \(i\)번째(\(1 \le i \le N\))로 갈 명소는 교차로 \((X_i, Y_i)\)에 있다. 여행에 걸리는 시간을 되도록 짧게 하려고, 지나가야 하는 길의 수를 줄이고 싶다. 명소를 미리 정한 순서로 돌기 위해 지나가야 하는 길의 수 합의 최솟값을 구하는 프로그램을 작성하라.

여행의 시작점은 교차로 \((X_1, Y_1)\)이다. 여행 도중에 초도 밖으로 나가서는 안 된다. 명소가 있는 교차로를 명소를 들르지 않고 지나칠 수도 있다.

같은 길을 두 번 이상 지나갈 수 있다. 그때 「길의 수 합」은 그 길을 지나간 횟수만큼 거듭 센다.