Verkefnalýsing

Just Oishi Ichigo-búgarðurinn (hér eftir JOI-búgarðurinn) er jarðarberjabúgarður sem er þekktur fyrir að vera langur og mjór frá austri til vesturs, og inngangur hans er á vestasta punkti búgarðsins. Hér eftir verður staðurinn sem er $k$ metrum austan við innganginn kallaður Punktur $k$.

Inni á JOI-búgarðinum vaxa $N$ jarðarber. Þau eru númeruð frá $1$ til $N$. Öll jarðarberin eru græn fram að tíma $0$. Jarðarber $i$ ($1 \le i \le N$) vex á Punkti $A_{i}$, og á tíma $T_{i}$ þroskast það og verður rautt.

Ekki er hægt að tína jarðarber á meðan þau eru græn. Með öðrum orðum er ekki hægt að tína jarðarber $i$ fyrr en á tíma $T_{i}$. Þú leggur af stað á tíma $0$ frá inngangi búgarðsins á Punkti $0$ og ferðast í austur–vestur-átt á allt að $1$ metra hraða á sekúndu á meðan þú tínir jarðarber. Tíminn sem fer í að tína jarðarber er hverfandi.

Gefnar eru upplýsingar um jarðarberjabúgarðinn. Skrifaðu forrit til að finna lágmarkstímann sem þarf til að tína öll jarðarberin í rauðu ástandi og koma aftur að innganginum.

Skorður

• $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$).
• Öll inntaksgildi eru heiltölur.

Inntak

Inntakið kemur úr staðalinntaki á eftirfarandi sniði:

N
A_1 T_1
A_2 T_2
:
A_N T_N

Úttak

Skrifaðu út í $1$ línu lágmarkstímann sem þarf til að tína öll jarðarberin í rauðu ástandi og koma aftur að innganginum.

Dæmi 1

Inntak

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

Úttak

20

Ef þú notar fyrstu $10$ sekúndurnar í að fara á Punkt $10$ geturðu týnt jarðarber $2, 4, 5, 7, 8, 9, 10$ í þessari röð á leiðinni. Ef þú notar síðan $10$ sekúndur í að fara til baka á Punkt $0$ geturðu týnt jarðarber $6, 3, 1$ í þessari röð á leiðinni. Þannig er hægt að tína öll $10$ jarðarberin í rauðu ástandi.

Dæmi 2

Inntak

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

Úttak

450

Með því að ferðast eins og lýst er hér að neðan er hægt að tína öll jarðarberin í rauðu ástandi á $450$ sekúndum:

1. Notaðu $45$ sekúndur til að fara á Punkt $45$. Þar sem tíminn er þá $45$ geturðu týnt jarðarber $10$. Eftir tínsluna notarðu $45$ sekúndur til að fara á Punkt $0$.
2. Eftir það notarðu $40$ sekúndur til að fara á Punkt $40$. Þar sem tíminn er þá $130$ geturðu týnt jarðarber $9$. Eftir tínsluna notarðu $40$ sekúndur til að fara á Punkt $0$.
3. Eftir það notarðu $35$ sekúndur til að fara á Punkt $35$. Þar sem tíminn er þá $205$ geturðu týnt jarðarber $8$. Eftir tínsluna notarðu $35$ sekúndur til að fara á Punkt $0$.
4. Eftir það notarðu $30$ sekúndur til að fara á Punkt $30$. Þar sem tíminn er þá $270$ geturðu týnt jarðarber $7$. Eftir tínsluna notarðu $30$ sekúndur til að fara á Punkt $0$.
5. Eftir það notarðu $25$ sekúndur til að fara á Punkt $25$. Þar sem tíminn er þá $325$ geturðu týnt jarðarber $6$. Eftir tínsluna notarðu $25$ sekúndur til að fara á Punkt $0$.
6. Eftir það notarðu $20$ sekúndur til að fara á Punkt $20$. Þar sem tíminn er þá $370$ geturðu týnt jarðarber $5$. Eftir tínsluna notarðu $20$ sekúndur til að fara á Punkt $0$.
7. Eftir það notarðu $15$ sekúndur til að fara á Punkt $15$. Þar sem tíminn er þá $405$ geturðu týnt jarðarber $4$. Eftir tínsluna notarðu $15$ sekúndur til að fara á Punkt $0$.
8. Eftir það notarðu $10$ sekúndur til að fara á Punkt $10$. Þar sem tíminn er þá $430$ geturðu týnt jarðarber $3$. Eftir tínsluna notarðu $10$ sekúndur til að fara á Punkt $0$.
9. Eftir það notarðu $5$ sekúndur til að fara á Punkt $5$. Þar sem tíminn er þá $445$ geturðu týnt jarðarber $2$. Eftir tínsluna notarðu $5$ sekúndur til að fara á Punkt $0$.
10. Þú kemur á Punkt $0$ nákvæmlega á tíma $450$, svo þú getur týnt jarðarber $1$. Þú kemur á Punkt $0$ á sama tíma og þú lýkur við að tína öll jarðarberin.

Dæmi 3

Inntak

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

Úttak

198