Alls eru $N + 1$ tegundir af mat: $N$ tegundir af mat sem eru númeraðar $1, 2, \dots, N$, og vatnshlaup. Fyrir $i = 1, 2, \dots, N$ er sætleiki matar $i$ jafn $A_i$ og styrkleiki hans (sterkleiki) er $B_i$. Sætleiki vatnshlaups er $0$ og styrkleiki þess er $0$.

UTPC-kun borðar fyrst vatnshlaup, borðar síðan mat $1, 2, \dots, N$ nákvæmlega einu sinni hvern í hvaða röð sem er, og borðar að lokum aftur vatnshlaup.

Hamingja UTPC-kun er $0$ strax eftir að hann borðar fyrsta vatnshlaupið. Eftir það breytist hamingja hans í hvert sinn sem hann borðar mat sem hér segir:

• Látum $a$ og $b$ vera sætleika og styrkleika matarins sem hann er að borða, og látum $a'$ og $b'$ vera sætleika og styrkleika matarins sem hann borðaði rétt á undan. Hamingja hans eykst um $\max(a - a', b - b')$. (Aukningin á hamingju getur verið neikvæð.)

Finndu mestu mögulegu lokahamingju UTPC-kun með því að velja bestu röðina til að borða mat $1, 2, \dots, N$.

Inntak

Inntakið er gefið á eftirfarandi sniði:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• Öll inntaksgildi eru heiltölur.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

Úttak

Prentaðu svarið á stakri línu.

Dæmi

Dæmi um inntak 1

4
1 4
3 1
2 3
3 4

Dæmi um úttak 1

6

Dæmi um inntak 2

3
1 2
2 1
1 2

Dæmi um úttak 2

3

Dæmi um inntak 3

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

Dæmi um úttak 3

18

Athugasemd

Í fyrsta dæminu er ein besta röðin til að borða matinn $1, 2, 3, 4$. Í þessu tilviki breytist hamingja UTPC-kun sem hér segir eftir að hann lýkur við að borða fyrsta vatnshlaupið:

• Borðar mat $1$: Hamingja hans eykst um $\max(1 - 0, 4 - 0) = 4$ og verður $4$.
• Borðar mat $2$: Hamingja hans eykst um $\max(3 - 1, 1 - 4) = 2$ og verður $6$.
• Borðar mat $3$: Hamingja hans eykst um $\max(2 - 3, 3 - 1) = 2$ og verður $8$.
• Borðar mat $4$: Hamingja hans eykst um $\max(3 - 2, 4 - 3) = 1$ og verður $9$.
• Borðar vatnshlaup: Hamingja hans eykst um $\max(0 - 3, 0 - 4) = -3$ og verður $6$.