마라톤 1

농장 젖소가 건강하지 않다고 생각한 농부 존은 젖소를 위한 마라톤 대회를 열었다. 존이 아끼는 젖소 박승원도 이 대회에 참가한다.

마라톤 코스는 체크포인트 $N$개로 이루어진다. 1번 체크포인트에서 출발해 번호 순서대로 모든 체크포인트를 지나 $N$번 체크포인트에 도착하면 마라톤이 끝난다. 게으른 박승원은 막상 대회에 나가려니 귀찮아져서 중간에 있는 체크포인트 한 개를 몰래 건너뛰려 한다. 다만 1번 체크포인트와 $N$번 체크포인트를 건너뛰면 너무 눈치가 보이니 이 두 체크포인트는 건너뛰지 않을 생각이다.

체크포인트 한 개를 건너뛰면서 달릴 수 있다면, 박승원이 달려야 하는 최소 거리는 얼마일까?

젖소 마라톤 대회는 서울 시내 한복판에서 열릴 예정이라 거리는 택시 거리(맨해튼 거리)로 계산한다. 즉 점 $(x_1, y_1)$과 점 $(x_2, y_2)$ 사이의 거리는 $|x_1 - x_2| + |y_1 - y_2|$다. ($|x|$는 절댓값 기호다.)

첫째 줄에 체크포인트의 수 $N$이 주어진다. ($3 \le N \le 100000$)

다음 $N$개 줄에 정수가 두 개씩 주어진다. $i$번째 줄의 첫 번째 정수는 체크포인트 $i$의 $x$좌표, 두 번째 정수는 $y$좌표다. ($-1000 \le x, y \le 1000$)

서로 다른 체크포인트의 좌표가 겹칠 수도 있다. 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트 하나만 건너뛰며, 같은 좌표에 있는 다른 체크포인트는 그대로 방문한다.

박승원이 체크포인트 한 개를 건너뛰고 달릴 수 있는 최소 거리를 출력한다.

첫 번째 예제에서 박승원은 2번 체크포인트나 3번 체크포인트를 건너뛸 수 있다. 2번 체크포인트를 건너뛰면 경로가 $(0, 0) \to (11, -1) \to (10, 0)$이 되고 거리는 14다. 이보다 짧게 달릴 수는 없다.