Duck Contest

Pizza Loving Duck

Program time limit: 1 seconds

Program memory limit: 256 MB

Frank the Space duck has landed on earth. He landed here in Sydney and found himself surrounded by buildings. As a huge fan of pizza, he wants to eat at least one pizza from every pizza place. To eat a pizza, Frank the duck needs to get on the straight line, and he can use his cosmic gaze to teleport the pizza from the pizza place, to his position. More formally, if the pizza place and Frank are both located on a horizontal street $x$, or if the pizza place and Frank are both located on a vertical street $y$, Frank can eat the pizza.

His friend space bear Noah, told him the pizza locations. To make navigation simple, he wants to visit the pizza places in the order Noah told him. In doing so, Noah denoted Frank's current position as $(0, 0)$. But since, Frank needs to go back to the Cosmic Pond Mallards (CPM), he wants to find the shortest distance he needs to travel.

Input

  • The first line contains an integer $N$, the number of pizza places.
  • The following $N$ lines contains two integers $x, y$ denoting the position of the $i$-th pizza place.

You should read from standard input.

Constraints

  • $1 \le N \le 20000$
  • $0 \le |x_i|, |y_i| \le 1000$

Additionally:

  • For Subtask $1$ ($70\%$ of points): $1 \le N \le 100$.
  • For Subtask $2$ ($30\%$ of points): there are no additional constraints.

Output

  • Output the minimum distance Frank needs to travel to eat pizza from all pizza places.

You should write to standard output.

Sample Input 1

4
1 1
5 5
1 1000
1000 1

Sample Output 1

10

Explanation

First, travel $1$ unit to reach point $(1, 0)$ and eat pizza from $(1, 1)$.

Second, travel $4$ units to reach point $(5, 0)$ and eat pizza from $(5, 5)$.

Third, travel $4$ units to reach point $(1, 0)$ and eat pizza from $(1, 1000)$.

Fourth, travel $1$ unit to reach point $(1, 1)$ and eat pizza from $(1000, 1)$.

Scoring

Your program will be tested on the sample cases and several hidden cases. If it produces the correct output for all test cases, it will be considered correct. Recall that your final score for this problem is the score of your highest-scoring submission.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .