Time limit: 2 seconds
Memory limit: 256 MB
Source: The second final exam of the 26th Computer Olympiad
After escaping from prison, the Dalton brothers have turned to extracting 2D oil wells to make ends meet. A two-dimensional oil well in the form of an infinite table with
n
n columns and
1
0
9
10
9
 It is the line above the first line, the ground level. Each column consists of specific amounts of soil, oil and rock. Based on the way oil is formed over time, in each column of the oil well, there is oil in a correct interval of the depth of the earth, which is this interval for the column
i
I am with
[
l
i
,
r
i
]
[l
i
​
 R
i
​
 ] and it means that from depth
l
i
l
i
​
 to the depth
r
i
r
i
​
 From the column
i
It consists of oil. As a result, this column includes
r
i
-
l
i
r
i
​
 -l
i
​
 It is a unit of oil. We also know that always from the surface of the earth to the depth of the beginning of oil, that is, the interval
[
0
,
l
i
]
[0, l
i
​
 ], composed of soil, and from the depth of the end of the oil to the end of the oil well, that is, the interval
[
r
i
,
1
0
9
]
[r
i
​
 , 10
9
 ], is made of stone. For example, if the oil interval in a column
[
1
,
3
]
[1,3], in that column, there is 1 unit of soil and 2 units of oil.



The Dalton brothers, who do not have much time to extract oil from the wells, work to extract oil in this way by choosing a number of columns in a row and digging the ground to a certain depth using an oil rig. If there is even one unit of stone in the sub-rectangle of the oil well that the oil drilling machine digs, the machine will be damaged, and that's why the Dalton brothers don't want there to be any stone under the rectangle that they dig. After digging a sub-rectangle from an oil well, all its soil units are destroyed, but all the oil units in it come out of the output of the oil rig and the Dalton brothers collect them.

After drilling a sub-rectangle of an oil well, the Dalton brothers can extract oil from all the holes connected to the oil reservoir using an oil skimmer. Please note that pores are all reservoirs containing oil from the matrix that have been exposed to air after subrectangular drilling. In other words, all the regions in the table that are one of the neighboring regions (adjacency in this question means lateral proximity. It means that two regions have a common side). They were located inside the carved sub-rectangle. After connecting to a hole, the oil trap device sucks all the units of oil that reach the hole through the reservoirs containing oil and takes them out of the outlet for Dalton brothers to collect. An oil-containing reservoir has a route to a hole if there is a sequence of oil-containing reservoirs starting from that hole and ending at the hole, such that any two consecutive members in the sequence are adjacent.

What is the maximum amount of oil that the Dalton brothers can collect?

input
In the first line of the input
n
n is the number of oil well columns. in
n
n next line of input, two natural numbers in each line
l
i
l
i
​
 and
r
i
r
i
​
 It is stated that the beginning and end of the interval formed by oil in the column
i
They show iam.
1
≤
n
≤
200

000
1≤n≤200 000
1
≤
l
i
≤
r
i
≤
1
0
9
1≤l
i
​
 ≤r
i
​
 ≤10
9


output
On the only output line, print the maximum amount of oil the Dalton brothers can collect.

Sub-issues
Constraint score subproblem
We don't have oil.
l
i
=
r
i
l
i
​
 =r
i
​
 )
We don't have 22 stones.
r
i
=
1
0
9
r
i
​
 =10
9
 )
We don't have soil
l
i
=
1
l
i
​
 =1)
4 12
n
≤
20
n≤20
5 21
n
≤
2

000
n≤2 000
6 61 without additional restrictions
Pay attention that there is always a layer of soil on the oil well and in the third sub-problem it is meant without considering that layer.

Example
Sample entry 1
11
2 2
2 4
3 4
3 3
4 5
4 5
3 4
3 5
4 6
3 5
1 2
Plain text
Sample output 1
11
Plain text
The sample input is the same as the first page of the question and shows the sub-rectangular red dashed line that Naftkan draws.   write in java 17