The "Worm" is an ancient creature. Tens of millions of years have passed, and the worm has long since vanished from the Earth, leaving little for us to know about it. Archaeologists have recently become interested in it because a batch of precious worm fossils has been discovered, preserving the worm in an almost complete form.

Theoretical scientists have summarized a general morphological model of the worm based on these fossils and concluded that the worm is the ancestor of the centipede! However, scientist J discovered some discrepancies between reality and theory. After carefully studying hundreds of worm fossils, he found that most of them do not perfectly fit the theoretical model. What factors caused this? Theoretical scientist K keenly pointed out that the morphology of the worm preserved in fossils is likely to have undergone various changes, and even the slightest change can cause it to deviate from the model.

Thus, a new problem arises for scientists: how large is the gap between a worm in a fossil and the theoretical model? Specifically, given the morphology $A$ of a worm fossil, find a morphology $B$ that conforms to the theoretical model such that $B$ is the most likely to have become morphology $A$ during the fossilization process.

The "Worm Morphological Model" proposed by theorists is as follows (as shown in the figure): The body consists of four main parts: head, tail, trunk, and feet.

1. The head and tail are represented by a pair of parallel line segments. The direction parallel to the head and tail is called the $x$ direction; the direction perpendicular to $x$ is the $y$ direction.
2. There are two non-intersecting polygonal chains connecting the head and tail. The region enclosed by these two chains and the head and tail segments is called the trunk. Both polygonal chains satisfy the following conditions: all corners are obtuse or straight angles, and they contain an odd number of segments, with the odd-numbered segments (counting from top to bottom) being perpendicular to the $x$ direction.
3. From each polygonal chain, a foot grows out from the side of the trunk at every even-numbered segment (counting from top to bottom). A foot is a trapezoid or rectangle with top and bottom bases parallel to the $x$ direction, and the side furthest from the trunk is perpendicular to the $x$ direction. Note: Feet cannot degenerate into triangles (i.e., the lengths of the bases are all greater than zero), and the number of feet on both sides of the trunk can be different. (As shown in the figure, there are 4 feet on the left and 5 feet on the right.)

It can be seen that in the $x-y$ Cartesian coordinate system, the boundaries of the solid region formed by the trunk and all feet are parallel or perpendicular to the coordinate axes. For convenience, we assume that the lengths of all these boundaries are positive integers. Therefore, we can consider each worm's body to be composed of several unit squares. Each unit square is uniquely determined by coordinates $(x, y)$. Let the distance between the head and tail be $n$. We can then describe a worm $B$ using $2n$ integers (as shown in the figure): divide $B$ into $n$ horizontal strips of width 1 along the direction parallel to the $x$-axis. Let $L_i$ be the $x$-coordinate of the leftmost square of the $i$-th strip, and $R_i$ be the $x$-coordinate of the rightmost square. Then $(n, L_1, L_2, \dots, L_n, R_1, R_2, \dots, R_n)$ defines a worm.

Due to the erosion of time, the shapes of the worms in the actual fossils found do not satisfy the rules of the theoretical model above; the bodies in some squares have been dissolved and eroded by certain minerals.

Geologists, physicists, and biologists have jointly concluded: 1. Erosion occurs square by square; only a whole square can be eroded. 2. Erosion occurs in steps; only one square is eroded at each step. 3. If the body becomes disconnected after removing a square, that square cannot be currently eroded. 4. If the left neighbor and the right neighbor of a square have not been eroded yet, that square cannot be currently eroded. 5. The squares adjacent to the head cannot all be eroded, and the squares adjacent to the tail cannot all be eroded.

If the above five conditions are met, we can still use $(n, L'_1, L'_2, \dots, L'_n, R'_1, R'_2, \dots, R'_n)$ to describe the morphology of a worm in a fossil, where $L'_i \le R'_i$.

Your task is to input the description $A $ of a worm in a fossil, find a description $B $ of a worm that satisfies the theoretical model, such that $B$ can become $A$ through the erosion process, and the cost of transforming $B$ into $A$ (the number of squares that must be eroded) is minimized. Output this minimum cost.

Input

The first line contains an integer $n$. The following $n$ lines each contain two integers $L'_i$ and $R'_i$, separated by a space. The input data is guaranteed to be valid.

Output

A single integer representing the minimum cost.

Examples

Input 1

7
4 4
3 4
3 5
1 3
2 2
2 4
3 3

Output 1

3

Note

As shown in the figure.

Constraints

30% of the data: $n \le 100$, $0 \le L'_i \le R'_i \le 100$ 50% of the data: $n \le 1000$, $0 \le L'_i \le R'_i \le 1000$ 70% of the data: $n \le 100000$, $0 \le L'_i \le R'_i \le 1000$ 100% of the data: $n \le 1000000$, $0 \le L'_i \le R'_i \le 1000000$

Subtasks

This problem has no partial points. Your program's output must be exactly the same as our answer to receive full marks; otherwise, no points will be awarded.

Figure 1. The Worm Morphological Model