Problembeskrivning

Just Oishi Ichigo-gården (hädanefter JOI-gården) är en jordgubbsodling som är känd för att vara lång och smal i öst-västlig riktning, och dess ingång ligger längsti väster på gården. Hädanefter kallas platsen som ligger $k$ meter öster om ingången för Punkt $k$.

Inne på JOI-gården växer $N$ jordgubbar. De är numrerade från $1$ till $N$. Alla jordgubbar är gröna fram till tidpunkt $0$. Jordgubbe $i$ ($1 \le i \le N$) växer vid Punkt $A_{i}$, och vid tidpunkt $T_{i}$ mognar den och blir röd.

Jordgubbar kan inte skördas medan de är gröna. Med andra ord kan jordgubbe $i$ inte skördas förrän vid tidpunkt $T_{i}$. Du startar vid tidpunkt $0$ från gårdens ingång vid Punkt $0$ och rör dig i öst-västlig riktning med en högsta hastighet av $1$ meter per sekund medan du skördar jordgubbar. Tiden det tar att plocka en jordgubbe kan försummas.

Givet informationen om jordgubbsodlingen, skriv ett program som beräknar den minsta tiden som krävs för att skörda alla jordgubbar i rött tillstånd och sedan återvända till ingången.

Begränsningar

• $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$).
• Alla indatavärden är heltal.

Indata

Indata ges från standardinmatningen i följande format:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Utdata

Skriv på $1$ rad ut den minsta tiden som krävs för att skörda alla jordgubbar i rött tillstånd och återvända till ingången.

Exempel 1

Indata

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

Utdata

20

Om du under de första $10$ sekunderna förflyttar dig till Punkt $10$ kan du på vägen dit skörda jordgubbarna $2, 4, 5, 7, 8, 9, 10$ i denna ordning. Om du därefter under $10$ sekunder återvänder till Punkt $0$ kan du på vägen tillbaka skörda jordgubbarna $6, 3, 1$ i denna ordning. På så sätt kan alla $10$ jordgubbar skördas i rött tillstånd.

Exempel 2

Indata

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

Utdata

450

Genom att förflytta dig på följande sätt kan du skörda alla jordgubbar i rött tillstånd på $450$ sekunder:

1. Förflytta dig under $45$ sekunder till Punkt $45$. Eftersom tidpunkten då är $45$ kan du skörda jordgubbe $10$. Efter skörden förflyttar du dig under $45$ sekunder tillbaka till Punkt $0$.
2. Därefter förflyttar du dig under $40$ sekunder till Punkt $40$. Eftersom tidpunkten då är $130$ kan du skörda jordgubbe $9$. Efter skörden förflyttar du dig under $40$ sekunder tillbaka till Punkt $0$.
3. Därefter förflyttar du dig under $35$ sekunder till Punkt $35$. Eftersom tidpunkten då är $205$ kan du skörda jordgubbe $8$. Efter skörden förflyttar du dig under $35$ sekunder tillbaka till Punkt $0$.
4. Därefter förflyttar du dig under $30$ sekunder till Punkt $30$. Eftersom tidpunkten då är $270$ kan du skörda jordgubbe $7$. Efter skörden förflyttar du dig under $30$ sekunder tillbaka till Punkt $0$.
5. Därefter förflyttar du dig under $25$ sekunder till Punkt $25$. Eftersom tidpunkten då är $325$ kan du skörda jordgubbe $6$. Efter skörden förflyttar du dig under $25$ sekunder tillbaka till Punkt $0$.
6. Därefter förflyttar du dig under $20$ sekunder till Punkt $20$. Eftersom tidpunkten då är $370$ kan du skörda jordgubbe $5$. Efter skörden förflyttar du dig under $20$ sekunder tillbaka till Punkt $0$.
7. Därefter förflyttar du dig under $15$ sekunder till Punkt $15$. Eftersom tidpunkten då är $405$ kan du skörda jordgubbe $4$. Efter skörden förflyttar du dig under $15$ sekunder tillbaka till Punkt $0$.
8. Därefter förflyttar du dig under $10$ sekunder till Punkt $10$. Eftersom tidpunkten då är $430$ kan du skörda jordgubbe $3$. Efter skörden förflyttar du dig under $10$ sekunder tillbaka till Punkt $0$.
9. Därefter förflyttar du dig under $5$ sekunder till Punkt $5$. Eftersom tidpunkten då är $445$ kan du skörda jordgubbe $2$. Efter skörden förflyttar du dig under $5$ sekunder tillbaka till Punkt $0$.
10. Du når Punkt $0$ exakt vid tidpunkt $450$, så du kan skörda jordgubbe $1$. Du anländer till Punkt $0$ samtidigt som du har skördat alla jordgubbar.

Exempel 3

Indata

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

Utdata

198