The Captain

Time limit2sMemory limit512 MB

Summary

Find the minimum total north-south distance the Captain must steer on a route from island 1 to island n, where he handles one axis per leg.

Level: Hard8 of 10
Topics: Graph, Shortest path, Dynamic programming
Solved: No attempts yet

Problem

Captain Byteasar sails the Byteic Sea together with his irreplaceable First Officer Bytec. The Byteic Sea has $n$ islands, numbered from 1 to $n$ . The Captain's ship is docked at island 1, and the Captain plans to sail to island $n$ .

During the voyage the ship always moves in one of the four cardinal directions: north, south, east, or west. At any moment either the Captain or the First Officer is at the helm. Every time the ship makes a 90 degree turn, the two of them swap places at the helm.

On the way, the ship may stop at other islands. After each stop the Captain decides whether he takes the helm first on the next leg or not. In other words, on every leg from one island to another, one sailor steers while the ship travels north or south and the other steers while it travels east or west. In particular, if a leg runs straight in a single cardinal direction, only one sailor steers on that leg.

The Captain wants to plan the route of the coming voyage and the division of labour so that he spends as little time at the helm as possible. He does not care how long the route becomes. The ship sails at a constant speed of one unit of distance per hour.

Input

The first line contains a single integer $n$ ( $2 \le n \le 200\,000$ ), the number of islands. The Byteic Sea carries a coordinate system whose axes are parallel to the cardinal directions, and every island is a single point. Each of the next $n$ lines describes one island: the $i$ -th of them contains two integers $x_i$ and $y_i$ ( $0 \le x_i, y_i \le 1\,000\,000\,000$ ), the coordinates of island $i$ . No two islands share the same coordinates.

Output

Print a single integer: the least number of hours the Captain has to steer the ship on the way from island 1 to island $n$ .

Hint

In the first sample the Captain may choose the route shown in the figure. On the way from island 1 (coordinates $(2, 2)$ ) to island 4 (coordinates $(7, 1)$ ) the Captain steers for only one hour, while the ship sails south. On the second leg he steers only while the ship moves east.

Examples3

Example 1
Input
```
5
2 2
1 1
4 5
7 1
6 7
```
Expected output
```
2
```
Example 2
Input
```
2
3 9
1000000000 9
```
Expected output
```
0
```
Example 3
Input
```
5
0 0
5 5
10 0
0 10
10 10
```
Expected output
```
0
```