Description

The Millennium Bug is an ancient creature that vanished from Earth tens of millions of years ago, and little is known about it. Paleobiologists have recently become interested in it because a set of precious Millennium Bug fossils was discovered, preserving the creature’s shape nearly intact.

Theoretical scientists have generalized a model of the Millennium Bug’s shape from these fossils, and on this basis determined that the Millennium Bug is the ancestor of the centipede. However, Scientist J found discrepancies between the model and reality. After closely studying hundreds of fossils, he discovered that most of them do not completely conform to the theoretical model. What caused this? Theoretical Scientist K pointed out that the shape of a Millennium Bug preserved in a fossil may have undergone various changes during fossilization, and even the slightest change could make it fail to match the model.

Thus a new problem arises for the scientists: how far is a fossilized Millennium Bug from the theoretical model? Specifically, given the shape $A$ of a Millennium Bug in a fossil, find a shape $B$ that conforms to the theoretical model such that $B$ is most likely to become $A$ during fossilization.

The theoretical “Millennium Bug shape model” is as follows (see the left figure): the body consists of four parts — head, tail, trunk, and legs.

• The head and the 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.
• Between the head and the tail, there are two disjoint polylines connecting them. Together with the head and tail segments, they bound a region called the trunk. Both polylines satisfy all of the following:
  • Every turn is an obtuse angle or a straight angle.
  • Each polyline consists of an odd number of segments.
  • Counting segments from top to bottom, the odd-numbered segments are perpendicular to the $x$ direction.
• On each polyline, a leg grows from every even-numbered segment (counted from top to bottom) on the side away from the trunk. Each leg is a trapezoid or rectangle whose top and bottom bases are parallel to the $x$ direction, and whose edge farthest from the trunk is perpendicular to the $x$ direction.

Note: A leg must not degenerate into a triangle (i.e., both base lengths are strictly greater than zero). The numbers of legs on the two sides of the trunk may differ. (In the above figure, there are $4$ legs on the left and $5$ on the right.)

In the $x$-$y$ Cartesian coordinate system, the boundary of the solid region formed by the trunk and all legs is parallel or perpendicular to the coordinate axes. For convenience, we assume all such boundary lengths are positive integers. Therefore, we can regard each Millennium Bug’s body as a shape formed by unit squares. Each unit square is uniquely determined by coordinates $(x, y)$. Let the distance between the head and the tail be $n$. Then we can describe a Millennium Bug $B$ using $2 \times n$ integers (see the right figure): cut $B$ into $n$ horizontal strips of width $1$ along directions parallel to the $x$ axis. In the $i$-th strip, let the $x$ coordinate of the leftmost cell be $L_i$, and the $x$ coordinate of the rightmost cell be $R_i$. Then $(n, L_1, L_2, \dots, L_n, R_1, R_2, \dots, R_n)$ determines a Millennium Bug.

Due to the erosion of time, the shape of the Millennium Bug in actual fossils does not follow the rules of the theoretical model. Some cells of the body have been dissolved and corroded by minerals. Geologists, physicists, and biologists have jointly concluded that:

• Corrosion happens at the granularity of cells; only an entire cell can be corroded.
• Corrosion proceeds step by step, and at each step only one cell is corroded.
• If removing a cell would disconnect the body, that cell will not be corroded at that time.
• If both the left neighbor and the right neighbor of a cell have not been corroded, then that cell will not be corroded at that time.
• The cells adjacent to the head cannot all be corroded, and the cells adjacent to the tail cannot all be corroded.

If the above five rules are satisfied, we can still describe the shape of a Millennium Bug in a fossil using $(n, L_1, L_2, \dots, L_n, R_1, R_2, \dots, R_n)$. Here $L_i \le R_i$.

For example, see the following figure:

Your task is: given a description $A$ of a Millennium Bug in a fossil, find a description $B$ that satisfies the theoretical model, such that $B$ can become $A$ through the corrosion process, and the cost of transforming $B$ into $A$ (the number of cells that must be corroded) is minimized. Output this minimum cost.

Input Format

The first line contains an integer $n$.

The following $n$ lines each contain two integers. In line $i$, the two integers are $L'_i$ and $R'_i$, separated by a space. It is guaranteed that the input testdata is valid.

Output Format

Output a single line containing one integer, the minimum cost.

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

3

Hint

Sample explanation:

As shown in the figure:

Scoring:

There is no partial score. Your program receives full score only if its output exactly matches our answer; otherwise you receive no score.

Constraints:

• For 30% of the testdata, $n \le 100$, $R'_i \le 100$.
• For 50% of the testdata, $n \le 1000$, $R'_i \le 1000$.
• For 70% of the testdata, $n \le 10^5$, $R'_i \le 1000$.
• For 100% of the testdata, $1 \le n \le 10^6$, $0 \le L'_i \le R'_i \le 10^6$.

Translated by ChatGPT 5