Problem F
Roller Coaster Assembly

To make sure that the LTH campus maintains its long tradition of being the best campus in Sweden, several roller coasters will be constructed on and around campus.

The roller coasters are constructed over an period of $N$ days, with one track segment being delivered from the factory every day. Each track segment is one-way and has two ends; trains enter the segment at one end and leave at the other. Every roller coaster must consist of at least two track segments.

The roller coasters are constructed one at a time, with each roller coaster being completed before construction of the next one is started. On the first day, the delivered track segment is used as the initial segment of the first roller coaster. For each of the following days there are two options available:

• Attach the new segment to the end of the current roller coaster, such that the new segment’s entrance is connected to the previous segment’s exit.

• Complete the current roller coaster by connecting its first and its final segments, and then use the newly delivered segment as the first segment of the next roller coaster. Since roller coasters must consist of at least two segments, this cannot be done on the final day or if the current roller coaster only has one segment.

After the final day, the last roller coaster is completed by attaching its first and final segments.

Every track segment has a speed limit at either end. The incoming limit $A$ applies to the end where the train enters the segment, and the outgoing limit $B$ applies to the end where the train leaves the segment. Where the train moves from one track segment to the next, it must obey both the outgoing limit $B$ of the segment it is leaving and the incoming limit $A’$ of the segment it is entering. Thus, the effective speed limit at the connection point of two segments is $\min \{ B, A’ \} $.

Since it’s more fun if the trains go fast, the roller coasters should be constructed to maximize the sum of speed limits at all connections. The number of roller coasters constructed doesn’t matter, and you know the speed limits for all $N$ track segments ahead of time.

Input

The first line of input contains one integer $N$ ($2 \leq N \leq 100\, 000$), the number of track segments. Then follow $N$ lines. The $i$th line contains the integers $A_ i$ and $B_ i$, the incoming and outgoing speed limits of the track segment delivered on the $i$th day, with $A_ i, B_ i \in \{ 1,\ldots , 10^9\} $.

Output

Output a single integer, the maximum possible sum of speed limits at the connections between track segments.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

Sample Description

In the first sample input, it is not possible to construct more than one roller coaster, since each coaster must consist of at least two track segments. Thus, the sum of speed limits is $\min (5, 2) + \min (7, 6) + \min (3, 1) = 9$.

In the second sample input, it is optimal to create $3$ roller coasters by starting new coasters on day $1$, day $5$ (when the segment $16, 12$ is delivered), and day $8$ (when the segment $7, 14$ is delivered).

3
1 5
2 7
6 3

9

9
19 3
16 9
2 1
5 19
16 12
11 1
9 16
7 14
18 18

74