Oppgavebeskrivelse

Just Oishi Ichigo-gården (heretter JOI-gården) er en jordbærgård som er kjent for å være lang og smal i øst–vest-retning, og inngangen ligger lengst mot vest på gården. Heretter kalles stedet som ligger $k$ meter øst for inngangen for Punkt $k$.

Inne på JOI-gården vokser det $N$ jordbær. De er nummerert fra $1$ til $N$. Alle jordbærene er grønne frem til tidspunkt $0$. Jordbær $i$ ($1 \le i \le N$) vokser ved Punkt $A_{i}$, og ved tidspunkt $T_{i}$ modnes det og blir rødt.

Jordbær kan ikke høstes mens de er grønne. Med andre ord kan jordbær $i$ ikke høstes før tidspunkt $T_{i}$. Du starter ved tidspunkt $0$ fra gårdens inngang ved Punkt $0$, og beveger deg i øst–vest-retning med en maksimal hastighet på $1$ meter per sekund mens du høster jordbær. Tiden det tar å høste et jordbær kan ses bort fra.

Gitt informasjonen om jordbærgården, skriv et program som finner den minste tiden det tar å høste alle jordbærene i rød tilstand og deretter vende tilbake til inngangen.

Begrensninger

• $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 inndataverdier er heltall.

Inndata

Inndata gis fra standard inndata på følgende format:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Utdata

Skriv ut på $1$ linje den minste tiden det tar å høste alle jordbærene i rød tilstand og vende tilbake til inngangen.

Eksempel 1

Inndata

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

Utdata

20

Hvis du bruker de første $10$ sekundene på å bevege deg til Punkt $10$, kan du på veien høste jordbærene $2, 4, 5, 7, 8, 9, 10$ i denne rekkefølgen. Hvis du deretter bruker $10$ sekunder på å gå tilbake til Punkt $0$, kan du på veien høste jordbærene $6, 3, 1$ i denne rekkefølgen. På denne måten kan alle de $10$ jordbærene høstes i rød tilstand.

Eksempel 2

Inndata

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

Utdata

450

Ved å bevege deg som følger kan du høste alle jordbærene i rød tilstand på $450$ sekunder:

1. Bruk $45$ sekunder på å bevege deg til Punkt $45$. Siden tidspunktet nå er $45$, kan du høste jordbær $10$. Etter høstingen bruker du $45$ sekunder på å bevege deg til Punkt $0$.
2. Deretter bruker du $40$ sekunder på å bevege deg til Punkt $40$. Siden tidspunktet nå er $130$, kan du høste jordbær $9$. Etter høstingen bruker du $40$ sekunder på å bevege deg til Punkt $0$.
3. Deretter bruker du $35$ sekunder på å bevege deg til Punkt $35$. Siden tidspunktet nå er $205$, kan du høste jordbær $8$. Etter høstingen bruker du $35$ sekunder på å bevege deg til Punkt $0$.
4. Deretter bruker du $30$ sekunder på å bevege deg til Punkt $30$. Siden tidspunktet nå er $270$, kan du høste jordbær $7$. Etter høstingen bruker du $30$ sekunder på å bevege deg til Punkt $0$.
5. Deretter bruker du $25$ sekunder på å bevege deg til Punkt $25$. Siden tidspunktet nå er $325$, kan du høste jordbær $6$. Etter høstingen bruker du $25$ sekunder på å bevege deg til Punkt $0$.
6. Deretter bruker du $20$ sekunder på å bevege deg til Punkt $20$. Siden tidspunktet nå er $370$, kan du høste jordbær $5$. Etter høstingen bruker du $20$ sekunder på å bevege deg til Punkt $0$.
7. Deretter bruker du $15$ sekunder på å bevege deg til Punkt $15$. Siden tidspunktet nå er $405$, kan du høste jordbær $4$. Etter høstingen bruker du $15$ sekunder på å bevege deg til Punkt $0$.
8. Deretter bruker du $10$ sekunder på å bevege deg til Punkt $10$. Siden tidspunktet nå er $430$, kan du høste jordbær $3$. Etter høstingen bruker du $10$ sekunder på å bevege deg til Punkt $0$.
9. Deretter bruker du $5$ sekunder på å bevege deg til Punkt $5$. Siden tidspunktet nå er $445$, kan du høste jordbær $2$. Etter høstingen bruker du $5$ sekunder på å bevege deg til Punkt $0$.
10. Du når Punkt $0$ nøyaktig ved tidspunkt $450$, så du kan høste jordbær $1$. Du ankommer Punkt $0$ samtidig som du er ferdig med å høste alle jordbærene.

Eksempel 3

Inndata

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