C. Broken Robot
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp has a robot that can move on a coordinate plane. Initially, the robot is located at point $$$(0, 0)$$$. The robot can move strictly to the right, strictly down, strictly to the left, or strictly up by a distance of one unit. Moving to the left and right corresponds to changing the $$$x$$$ coordinate by $$$-1$$$ and $$$+1$$$, respectively. Moving down and up corresponds to changing the $$$y$$$ coordinate by $$$-1$$$ and $$$+1$$$, respectively.

One of the robot's wheels is malfunctioning, so it is limited in its movements and can move as follows:

  • the first movement of the robot must be either to the right or down;
  • after moving to the right, the robot can move either to the right or down;
  • after moving down, the robot can move either down or to the left;
  • after moving to the left, the robot can move either to the left or up;
  • after moving up, it can move either up or to the right.

The robot is given a sequence of points. It must visit the first point in the sequence, then the second point, and so on.

Your task is to determine the minimum time it takes for the robot to visit all the points, starting at the cell $$$(0, 0)$$$.

Note that if the robot has already visited a point that appears later in the given sequence, it must still visit it when necessary. Refer to the explanations for the examples for a better understanding of the statement.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points that the robot has to visit.

In the $$$i$$$-th of the following lines, there are two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^{9} \le x_i, y_i \le 10^{9}$$$) — the coordinates of the point that the robot must visit in the $$$i$$$-th order.

Note that the points can be repeated. The robot will have to visit the point again each time it appears in the given sequence of points.

Output

Output one integer — the minimum number of moves it takes for the broken robot to visit all the specified points in the required order.

Examples
Input
4
2 0
1 1
1 5
1 5
Output
10
Input
3
0 0
-4 -2
0 0
Output
12
Input
2
1000000000 1000000000
-1000000000 -1000000000
Output
6000000004
Note

In the first example, the robot can move to the right twice to reach the first point $$$(2, 0)$$$. Then, the robot can move down once, then left once, and then up twice to reach the second point $$$(1, 1)$$$. After that, the robot can move up four times to reach the third point $$$(1, 5)$$$. Then, the robot doesn't need to move because the fourth point coincides with the third point, and it is already there. Thus, the robot will visit all the points in $$$2 + 4 + 4 = 10$$$ moves.

In the second example, the robot is already at the point $$$(0, 0)$$$, so the first point is considered visited. Then, the robot can move down twice, and then move left four times to reach the second point $$$(-4, -2)$$$. After that, the robot can move up twice and move right four times to reach the third point $$$(0, 0)$$$. Thus, the robot will visit all the points in $$$6 + 6 = 12$$$ moves.