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 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.
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 one integer — the minimum number of moves it takes for the broken robot to visit all the specified points in the required order.
4 2 0 1 1 1 5 1 5
10
3 0 0 -4 -2 0 0
12
2 1000000000 1000000000 -1000000000 -1000000000
6000000004
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.
Name |
---|