농부 존은 소들의 건강 상태가 좋지 않은 것을 걱정하여 다양한 운동 프로그램에 소들을 등록시켰습니다.

그중 존이 가장 아끼는 암소 베시는 농장 근처 도심에서 열리는 마라톤 대회에 참가를 준비하고 있습니다.

마라톤 코스는 \(1\)번부터 \(N\)번까지 순서대로 방문해야 하는 \(N\)개의 체크포인트로 구성되어 있으며, \(1\)번 체크포인트가 출발점, \(N\)번 체크포인트가 결승점입니다. (\(3 \le N \le 100,000\))

베시는 본래 모든 체크포인트를 순서대로 방문해야 하지만, 게으른 베시는 최대 \(1\)개의 체크포인트를 건너뛰어 총 이동 거리를 줄이기로 마음먹었습니다.

단, 눈에 너무 띄지 않도록 출발점(\(1\)번)과 결승점(\(N\)번) 체크포인트는 건너뛸 수 없습니다.

마라톤 코스는 격자 형태의 도로망 위에 구축되어 있어, 두 체크포인트 \((x_1, y_1)\)과 \((x_2, y_2)\) 사이의 거리는 맨해튼 거리인 \(|x_1 - x_2| + |y_1 - y_2|\)로 계산됩니다.

베시가 최대 \(1\)개의 체크포인트를 건너뛸 때 완주할 수 있는 최소 이동 거리를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 체크포인트의 개수 \(N\)이 주어진다. (\(3 \le N \le 100,000\))

둘째 줄부터 \(N\)개의 줄에 걸쳐 각 체크포인트의 좌표 \(x, y\)가 공백으로 구분되어 주어진다. (\(-1000 \le x, y \le 1000\)) 체크포인트는 방문해야 하는 순서대로 입력된다.

출력

베시가 최대 \(1\)개의 체크포인트를 건너뛰었을 때 이동해야 하는 최소 거리를 출력한다.

예제 입력 1

4
0 0
8 3
11 -1
10 0

예제 출력 1

14

출처

USACO 2014 December Contest, Bronze