Millennium Worm

The millennium worm is an ancient life form that vanished from the surface of the earth tens of millions of years ago, so little is known about it. Archaeologists became interested in the species after several precious millennium worm fossils were discovered. These fossils preserve nearly the entire form of the animal.

Theoretical scientists used the fossils to build a morphological model and concluded that the millennium worm is the ancestor of the centipede. Scientist J found discrepancies between practice and theory. After studying hundreds of fossils, he found that most millennium worm structures do not fully match the theoretical model. Theoretical scientist K points out that a fossil may undergo various changes while it is in fossil form. Even the subtlest change can make it inconsistent with the model.

This creates a new problem: for a given fossilized millennium worm, predict how different it is from the theoretical model. Specifically, given the shape of a fossil A, find a shape B that fits the theoretical model and is the most likely shape to turn into A during fossilization.

The millennium worm physical features model proposed by theoretical scientists is shown in the left figure. Its body has four major components: the head, tail, torso, and feet.

1. The head and tail are a pair of parallel line segments. The direction parallel to the head and tail is the x direction, and the direction perpendicular to it is the y direction.
2. The head and tail are joined by two non-intersecting folded line segments. These lines, together with the head and tail, enclose a region called the torso. Each folded angle is either obtuse or straight. There must be an odd number of line segments, and an odd number of them must be perpendicular to the x direction, counted from top to bottom.
3. Counting from top to bottom, the torso at each even-numbered line segment has a single foot growing out of one side. The top and bottom sides of the foot are parallel to the x direction, and the foot is either trapezoidal or rectangular. The side facing away from the torso is perpendicular to the x direction.

A foot cannot be a triangle, so the base of each foot has a length greater than zero. The number of feet on each side of the torso may differ.

In the xy coordinate system, each border of the solid region formed by the torso and feet is parallel or perpendicular to an axis. For simplicity, the lengths of these borders are positive integers. So the body of each millennium worm is a set of unit squares, and each unit is identified by its coordinates (x, y). Let the distance between the head and tail be $n$. Then $2n$ integers describe one millennium worm B. Split B into $n$ strips of width 1 parallel to the x direction. Let the leftmost unit of strip $i$ have x-coordinate $L_i$, and the rightmost unit have x-coordinate $R_i$. Then $(n, L_1, L_2, ..., L_n, R_1, R_2, ..., R_n)$ specifies one millennium worm.

Erosion over the years has changed the fossil, so its shape does not satisfy the theoretical model. Some cells of its body have been corroded by minerals.

Geologists, physicists, and biologists have concluded the following.

1. Corrosion affects individual cells. Only whole unit cells can be corroded.
2. Corrosion happens in steps, and exactly one cell is corroded per step.
3. If the body stays connected after removing a cell, that cell cannot be corroded.
4. If neither the left neighbor nor the right neighbor of a cell has been corroded, that cell cannot currently be corroded.
5. The cells neighboring the head cannot all be corroded. The cells neighboring the tail cannot all be corroded.

If these five conditions hold, the fossil can be specified as $(n, L'_1, L'_2, ..., L'_n, R'_1, R'_2, ..., R'_n)$ with $L'_i \le R'_i$. The figure below shows an example.

Given the specification $\langle n, L', R' \rangle$ of a fossil A, find a specification $\langle n, L, R \rangle$ of a worm B that fits the theoretical description, such that B can be transformed into A by the corrosion process and the cost of transforming B into A (the number of cells that must be corroded) is minimized. Output this minimum number of steps.

The first line contains a single integer $n$.

Each of the following $n$ lines contains two integers $L'_i$ and $R'_i$, separated by a single space. The $i$-th of these lines gives $L'_i$ and $R'_i$.

Print a single integer on one line: the minimum cost.

$n \le 1000000$

$0 \le L'_i \le R'_i \le 1000000$

The input data is guaranteed to be valid.