Testo del problema

La fattoria Just Oishi Ichigo (di seguito Fattoria JOI) è una coltivazione di fragole famosa per essere lunga e stretta da est a ovest, e il suo ingresso si trova nel punto più occidentale della fattoria. Nel seguito, il luogo situato $k$ metri a est dell'ingresso verrà chiamato Punto $k$.

All'interno della Fattoria JOI crescono $N$ fragole, numerate da $1$ a $N$. Tutte le fragole sono acerbe (verdi) fino all'istante $0$. La fragola $i$ ($1 \le i \le N$) cresce nel Punto $A_{i}$ e all'istante $T_{i}$ matura diventando rossa.

Le fragole non possono essere raccolte mentre sono verdi. In altre parole, la fragola $i$ non può essere raccolta fino all'istante $T_{i}$. Partendo all'istante $0$ dall'ingresso della fattoria situato nel Punto $0$, ti muovi in direzione est-ovest a una velocità massima di $1$ metro al secondo raccogliendo le fragole. Il tempo necessario per raccogliere una fragola è trascurabile.

Date le informazioni sulla coltivazione di fragole, scrivi un programma che trovi il tempo minimo necessario per raccogliere tutte le fragole quando sono rosse e fare ritorno all'ingresso.

Vincoli

• $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$).
• Tutti i valori in input sono interi.

Input

L'input viene fornito dallo standard input nel seguente formato:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Output

Stampa su $1$ riga il tempo minimo necessario per raccogliere tutte le fragole quando sono rosse e tornare all'ingresso.

Esempio 1

Input

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

Output

20

Impiegando i primi $10$ secondi per spostarti fino al Punto $10$, lungo il tragitto puoi raccogliere le fragole $2, 4, 5, 7, 8, 9, 10$ in quest'ordine. Successivamente, impiegando $10$ secondi per tornare al Punto $0$, lungo il tragitto puoi raccogliere le fragole $6, 3, 1$ in quest'ordine. In questo modo tutte le $10$ fragole possono essere raccolte quando sono rosse.

Esempio 2

Input

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

Output

450

Muovendoti nel modo seguente, puoi raccogliere tutte le fragole quando sono rosse in $450$ secondi:

1. Impiega $45$ secondi per spostarti fino al Punto $45$. Poiché ora è l'istante $45$, puoi raccogliere la fragola $10$. Dopo la raccolta, impiega $45$ secondi per tornare al Punto $0$.
2. Successivamente, impiega $40$ secondi per spostarti fino al Punto $40$. Poiché ora è l'istante $130$, puoi raccogliere la fragola $9$. Dopo la raccolta, impiega $40$ secondi per tornare al Punto $0$.
3. Successivamente, impiega $35$ secondi per spostarti fino al Punto $35$. Poiché ora è l'istante $205$, puoi raccogliere la fragola $8$. Dopo la raccolta, impiega $35$ secondi per tornare al Punto $0$.
4. Successivamente, impiega $30$ secondi per spostarti fino al Punto $30$. Poiché ora è l'istante $270$, puoi raccogliere la fragola $7$. Dopo la raccolta, impiega $30$ secondi per tornare al Punto $0$.
5. Successivamente, impiega $25$ secondi per spostarti fino al Punto $25$. Poiché ora è l'istante $325$, puoi raccogliere la fragola $6$. Dopo la raccolta, impiega $25$ secondi per tornare al Punto $0$.
6. Successivamente, impiega $20$ secondi per spostarti fino al Punto $20$. Poiché ora è l'istante $370$, puoi raccogliere la fragola $5$. Dopo la raccolta, impiega $20$ secondi per tornare al Punto $0$.
7. Successivamente, impiega $15$ secondi per spostarti fino al Punto $15$. Poiché ora è l'istante $405$, puoi raccogliere la fragola $4$. Dopo la raccolta, impiega $15$ secondi per tornare al Punto $0$.
8. Successivamente, impiega $10$ secondi per spostarti fino al Punto $10$. Poiché ora è l'istante $430$, puoi raccogliere la fragola $3$. Dopo la raccolta, impiega $10$ secondi per tornare al Punto $0$.
9. Successivamente, impiega $5$ secondi per spostarti fino al Punto $5$. Poiché ora è l'istante $445$, puoi raccogliere la fragola $2$. Dopo la raccolta, impiega $5$ secondi per tornare al Punto $0$.
10. Raggiungi il Punto $0$ esattamente all'istante $450$, quindi puoi raccogliere la fragola $1$. Sei arrivato al Punto $0$ nello stesso istante in cui hai completato la raccolta di tutte le fragole.

Esempio 3

Input

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

Output

198