Tehtävänanto

Just Oishi Ichigo -tila (jäljempänä JOI-tila) on mansikkatila, joka on kuuluisa kapeasta ja pitkästä itä–länsi-suuntaisesta muodostaan, ja sen sisäänkäynti sijaitsee tilan läntisimmässä pisteessä. Jäljempänä sisäänkäynnistä $k$ metriä itään sijaitsevaa paikkaa kutsutaan pisteeksi $k$.

JOI-tilalla kasvaa $N$ mansikkaa. Ne on numeroitu $1$:stä $N$:ään. Kaikki mansikat ovat raakoja (vihreitä) ajanhetkeen $0$ asti. Mansikka $i$ ($1 \le i \le N$) kasvaa pisteessä $A_{i}$, ja ajanhetkellä $T_{i}$ se kypsyy punaiseksi.

Mansikoita ei voi poimia niiden ollessa vihreitä. Toisin sanoen mansikkaa $i$ ei voi poimia ennen ajanhetkeä $T_{i}$. Lähdet ajanhetkellä $0$ pisteessä $0$ sijaitsevalta tilan sisäänkäynniltä ja liikut itä–länsi-suunnassa enintään $1$ metrin sekuntinopeudella poimien samalla mansikoita. Mansikan poimimiseen kuluva aika voidaan jättää huomiotta.

Kun mansikkatilan tiedot annetaan, kirjoita ohjelma, joka etsii pienimmän mahdollisen ajan, joka kuluu kaikkien mansikoiden poimimiseen punaisina ja palaamiseen takaisin sisäänkäynnille.

Rajoitukset

• $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$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Tuloste

Tulosta $1$ riville pienin aika, joka kuluu kaikkien mansikoiden poimimiseen punaisina ja palaamiseen sisäänkäynnille.

Esimerkki 1

Syöte

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

Tuloste

20

Jos liikut ensimmäisten $10$ sekunnin aikana pisteeseen $10$, voit matkan varrella poimia mansikat $2, 4, 5, 7, 8, 9, 10$ tässä järjestyksessä. Kun sen jälkeen palaat $10$ sekunnissa pisteeseen $0$, voit matkan varrella poimia mansikat $6, 3, 1$ tässä järjestyksessä. Näin kaikki $10$ mansikkaa saadaan poimittua punaisina.

Esimerkki 2

Syöte

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

Tuloste

450

Liikkumalla seuraavasti kaikki mansikat voidaan poimia punaisina $450$ sekunnissa:

1. Siirry $45$ sekunnissa pisteeseen $45$. Koska ajanhetki on tällöin $45$, voit poimia mansikan $10$. Poimimisen jälkeen siirry $45$ sekunnissa pisteeseen $0$.
2. Sen jälkeen siirry $40$ sekunnissa pisteeseen $40$. Koska ajanhetki on tällöin $130$, voit poimia mansikan $9$. Poimimisen jälkeen siirry $40$ sekunnissa pisteeseen $0$.
3. Sen jälkeen siirry $35$ sekunnissa pisteeseen $35$. Koska ajanhetki on tällöin $205$, voit poimia mansikan $8$. Poimimisen jälkeen siirry $35$ sekunnissa pisteeseen $0$.
4. Sen jälkeen siirry $30$ sekunnissa pisteeseen $30$. Koska ajanhetki on tällöin $270$, voit poimia mansikan $7$. Poimimisen jälkeen siirry $30$ sekunnissa pisteeseen $0$.
5. Sen jälkeen siirry $25$ sekunnissa pisteeseen $25$. Koska ajanhetki on tällöin $325$, voit poimia mansikan $6$. Poimimisen jälkeen siirry $25$ sekunnissa pisteeseen $0$.
6. Sen jälkeen siirry $20$ sekunnissa pisteeseen $20$. Koska ajanhetki on tällöin $370$, voit poimia mansikan $5$. Poimimisen jälkeen siirry $20$ sekunnissa pisteeseen $0$.
7. Sen jälkeen siirry $15$ sekunnissa pisteeseen $15$. Koska ajanhetki on tällöin $405$, voit poimia mansikan $4$. Poimimisen jälkeen siirry $15$ sekunnissa pisteeseen $0$.
8. Sen jälkeen siirry $10$ sekunnissa pisteeseen $10$. Koska ajanhetki on tällöin $430$, voit poimia mansikan $3$. Poimimisen jälkeen siirry $10$ sekunnissa pisteeseen $0$.
9. Sen jälkeen siirry $5$ sekunnissa pisteeseen $5$. Koska ajanhetki on tällöin $445$, voit poimia mansikan $2$. Poimimisen jälkeen siirry $5$ sekunnissa pisteeseen $0$.
10. Saavut pisteeseen $0$ täsmälleen ajanhetkellä $450$, joten voit poimia mansikan $1$. Saavuit pisteeseen $0$ samalla hetkellä, kun sait kaikki mansikat poimittua.

Esimerkki 3

Syöte

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

Tuloste

198