Problem description

Krasnoludzki Zarząd Podziemi Wrocławskich podjął ostatnio decyzję o budowie dwóch tuneli pod Wrocławiem (nie wiadomo do końca po co, może jakieś metro…).

We wrocławskich podziemiach mieszka N krasnali, z których każdy, wedle zarządzenia, zostanie przydzielony do budowy dokładnie jednego tunelu. Dodatkowo, w zarządzeniu znajduje się warunek, że do każdego tunelu przydzielony zostanie co najmniej jeden krasnal.

Niestety, jak to zwykle bywa, prace nie mogą się tak od razu rozpocząć pierwszego dnia. Mianowicie, każdy z krasnali przedstawił zarządowi przedział dni [P_i,K_i], w których jest on dostępny w tygodniu robót (warto zauważyć, że krasnoludzki tydzień ma 10⁹ dni). Aby nie doszło do buntu, każdego dnia prac w danym tunelu wszystkie przydzielone do niego krasnoludki muszą stawić się w pracy.

Teraz zarząd ma nie lada zagwozdkę. Chciałby on rozdzielić krasnoludki do pracy pomiędzy dwa tunele w taki sposób, żeby sumaryczna liczba dni pracy w obu tunelach była jak największa (dni dla obu tuneli liczymy niezależnie). Pomóż zarządowi: wyznacz maksymalną sumaryczną liczbę dni pracy w obu tunelach.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę krasnali we Wrocławiu.

W kolejnych N wierszach znajdują się po dwie liczby całkowite P_i oraz K_i, oznaczające, że krasnoludek o numerze i może pracować w dniach od P_i do K_i włącznie.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca maksymalną sumaryczną liczbę dni, w których mogą odbywać się prace w tunelach.

Ograniczenia

2 ≤ N ≤ 100 000, 1 ≤ P_i ≤ K_i ≤ 10⁹.

Przykłady

4
4 7
1 4
5 8
2 5

6

4
1 20
2 19
3 18
4 17

34

10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

540049931

3
2 10
3 5
7 9

9