Ruokia on yhteensä $N + 1$ lajia: $N$ ruokalajia, jotka on numeroitu $1, 2, \dots, N$, sekä vesihyytelö. Jokaiselle $i = 1, 2, \dots, N$ ruoan $i$ makeus on $A_i$ ja sen tulisuus on $B_i$. Vesihyytelön makeus on $0$ ja sen tulisuus on $0$.

UTPC-kun syö ensin vesihyytelöä, syö sitten ruoat $1, 2, \dots, N$ täsmälleen kerran kunkin haluamassaan järjestyksessä, ja lopuksi syö jälleen vesihyytelöä.

UTPC-kunin onnellisuus on $0$ välittömästi ensimmäisen vesihyytelön syömisen jälkeen. Sen jälkeen aina kun hän syö ruoan, hänen onnellisuutensa muuttuu seuraavasti:

• Olkoot $a$ ja $b$ hänen parhaillaan syömänsä ruoan makeus ja tulisuus, ja olkoot $a'$ ja $b'$ hänen välittömästi sitä ennen syömänsä ruoan makeus ja tulisuus. Hänen onnellisuutensa kasvaa määrällä $\max(a - a', b - b')$. (Onnellisuuden kasvu voi olla negatiivinen.)

Etsi UTPC-kunin suurin mahdollinen lopullinen onnellisuus valitsemalla optimaalinen järjestys ruokien $1, 2, \dots, N$ syömiselle.

Syöte

Syöte annetaan seuraavassa muodossa:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• Kaikki syötteen arvot ovat kokonaislukuja.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

Tuloste

Tulosta vastaus yhdelle riville.

Esimerkit

Esimerkkisyöte 1

4
1 4
3 1
2 3
3 4

Esimerkkituloste 1

6

Esimerkkisyöte 2

3
1 2
2 1
1 2

Esimerkkituloste 2

3

Esimerkkisyöte 3

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

Esimerkkituloste 3

18

Huomautus

Ensimmäisessä esimerkissä eräs optimaalinen järjestys syödä ruoat on $1, 2, 3, 4$. Tässä tapauksessa UTPC-kunin onnellisuus muuttuu ensimmäisen vesihyytelön syömisen jälkeen seuraavasti:

• Syö ruoan $1$: Hänen onnellisuutensa kasvaa määrällä $\max(1 - 0, 4 - 0) = 4$, ja siitä tulee $4$.
• Syö ruoan $2$: Hänen onnellisuutensa kasvaa määrällä $\max(3 - 1, 1 - 4) = 2$, ja siitä tulee $6$.
• Syö ruoan $3$: Hänen onnellisuutensa kasvaa määrällä $\max(2 - 3, 3 - 1) = 2$, ja siitä tulee $8$.
• Syö ruoan $4$: Hänen onnellisuutensa kasvaa määrällä $\max(3 - 2, 4 - 3) = 1$, ja siitä tulee $9$.
• Syö vesihyytelöä: Hänen onnellisuutensa kasvaa määrällä $\max(0 - 3, 0 - 4) = -3$, ja siitä tulee $6$.