Aufgabenstellung

Die Just-Oishi-Ichigo-Farm (im Folgenden JOI-Farm) ist eine Erdbeerfarm, die dafür bekannt ist, sich lang und schmal von Ost nach West zu erstrecken, wobei ihr Eingang ganz im Westen der Farm liegt. Im Folgenden wird der Ort, der $k$ Meter östlich vom Eingang liegt, als Punkt $k$ bezeichnet.

Auf der JOI-Farm wachsen $N$ Erdbeeren. Sie sind von $1$ bis $N$ nummeriert. Alle Erdbeeren sind bis zum Zeitpunkt $0$ grün. Erdbeere $i$ ($1 \le i \le N$) wächst bei Punkt $A_{i}$ und wird zum Zeitpunkt $T_{i}$ reif und damit rot.

Erdbeeren können im grünen Zustand nicht geerntet werden. Das heißt, Erdbeere $i$ kann erst ab dem Zeitpunkt $T_{i}$ geerntet werden. Du startest zum Zeitpunkt $0$ am Farmeingang bei Punkt $0$ und bewegst dich mit einer Höchstgeschwindigkeit von $1$ Meter pro Sekunde in Ost-West-Richtung, während du Erdbeeren erntest. Die Zeit, die für das Ernten einer Erdbeere benötigt wird, kann vernachlässigt werden.

Schreibe ein Programm, das anhand der Informationen über die Erdbeerfarm die minimale Zeit berechnet, die benötigt wird, um alle Erdbeeren im roten Zustand zu ernten und anschließend zum Eingang zurückzukehren.

Bedingungen

• $1 \le N \le 100\,000$.
• $0 \le A_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$).
• $0 \le T_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$).
• Alle Eingabewerte sind ganze Zahlen.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Ausgabe

Gib in $1$ Zeile die minimale Zeit aus, die benötigt wird, um alle Erdbeeren im roten Zustand zu ernten und anschließend zum Eingang zurückzukehren.

Beispiel 1

Eingabe

10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3

Ausgabe

20

Wenn du in den ersten $10$ Sekunden zu Punkt $10$ gehst, kannst du unterwegs die Erdbeeren $2, 4, 5, 7, 8, 9, 10$ in dieser Reihenfolge ernten. Wenn du danach in $10$ Sekunden zu Punkt $0$ zurückkehrst, kannst du unterwegs die Erdbeeren $6, 3, 1$ in dieser Reihenfolge ernten. Auf diese Weise können alle $10$ Erdbeeren im roten Zustand geerntet werden.

Beispiel 2

Eingabe

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

Ausgabe

450

Wenn du dich wie folgt bewegst, kannst du alle Erdbeeren in $450$ Sekunden im roten Zustand ernten:

1. Gehe in $45$ Sekunden zu Punkt $45$. Da es nun Zeitpunkt $45$ ist, kann Erdbeere $10$ geerntet werden. Gehe nach dem Ernten in $45$ Sekunden zurück zu Punkt $0$.
2. Gehe danach in $40$ Sekunden zu Punkt $40$. Da es nun Zeitpunkt $130$ ist, kann Erdbeere $9$ geerntet werden. Gehe nach dem Ernten in $40$ Sekunden zurück zu Punkt $0$.
3. Gehe danach in $35$ Sekunden zu Punkt $35$. Da es nun Zeitpunkt $205$ ist, kann Erdbeere $8$ geerntet werden. Gehe nach dem Ernten in $35$ Sekunden zurück zu Punkt $0$.
4. Gehe danach in $30$ Sekunden zu Punkt $30$. Da es nun Zeitpunkt $270$ ist, kann Erdbeere $7$ geerntet werden. Gehe nach dem Ernten in $30$ Sekunden zurück zu Punkt $0$.
5. Gehe danach in $25$ Sekunden zu Punkt $25$. Da es nun Zeitpunkt $325$ ist, kann Erdbeere $6$ geerntet werden. Gehe nach dem Ernten in $25$ Sekunden zurück zu Punkt $0$.
6. Gehe danach in $20$ Sekunden zu Punkt $20$. Da es nun Zeitpunkt $370$ ist, kann Erdbeere $5$ geerntet werden. Gehe nach dem Ernten in $20$ Sekunden zurück zu Punkt $0$.
7. Gehe danach in $15$ Sekunden zu Punkt $15$. Da es nun Zeitpunkt $405$ ist, kann Erdbeere $4$ geerntet werden. Gehe nach dem Ernten in $15$ Sekunden zurück zu Punkt $0$.
8. Gehe danach in $10$ Sekunden zu Punkt $10$. Da es nun Zeitpunkt $430$ ist, kann Erdbeere $3$ geerntet werden. Gehe nach dem Ernten in $10$ Sekunden zurück zu Punkt $0$.
9. Gehe danach in $5$ Sekunden zu Punkt $5$. Da es nun Zeitpunkt $445$ ist, kann Erdbeere $2$ geerntet werden. Gehe nach dem Ernten in $5$ Sekunden zurück zu Punkt $0$.
10. Du erreichst Punkt $0$ genau zum Zeitpunkt $450$, sodass du Erdbeere $1$ ernten kannst. Gleichzeitig mit der Ernte aller Erdbeeren bist du wieder bei Punkt $0$ angekommen.

Beispiel 3

Eingabe

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

Ausgabe

198