Es gibt insgesamt $N + 1$ Arten von Speisen: $N$ Arten von Speisen, die mit $1, 2, \dots, N$ nummeriert sind, sowie Wassergelee. Für $i = 1, 2, \dots, N$ beträgt die Süße von Speise $i$ gleich $A_i$ und ihre Schärfe $B_i$. Die Süße von Wassergelee ist $0$ und seine Schärfe ist $0$.

UTPC-kun isst zuerst Wassergelee, dann isst er die Speisen $1, 2, \dots, N$ jeweils genau einmal in beliebiger Reihenfolge, und schließlich isst er erneut Wassergelee.

Unmittelbar nach dem Verzehr des ersten Wassergelees beträgt die Zufriedenheit von UTPC-kun $0$. Danach ändert sich seine Zufriedenheit jedes Mal, wenn er eine Speise isst, wie folgt:

• Seien $a$ und $b$ die Süße und die Schärfe der Speise, die er gerade isst, und seien $a'$ und $b'$ die Süße und die Schärfe der Speise, die er unmittelbar davor gegessen hat. Seine Zufriedenheit erhöht sich um $\max(a - a', b - b')$. (Der Zuwachs an Zufriedenheit kann auch negativ sein.)

Bestimme die maximal mögliche Endzufriedenheit von UTPC-kun, indem du die optimale Reihenfolge für den Verzehr der Speisen $1, 2, \dots, N$ wählst.

Eingabe

Die Eingabe erfolgt im folgenden Format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• Alle Eingabewerte sind ganze Zahlen.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

Ausgabe

Gib die Antwort in einer einzigen Zeile aus.

Beispiele

Beispieleingabe 1

4
1 4
3 1
2 3
3 4

Beispielausgabe 1

6

Beispieleingabe 2

3
1 2
2 1
1 2

Beispielausgabe 2

3

Beispieleingabe 3

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

Beispielausgabe 3

18

Hinweis

Im ersten Beispiel ist $1, 2, 3, 4$ eine optimale Reihenfolge für den Verzehr der Speisen. In diesem Fall ändert sich die Zufriedenheit von UTPC-kun nach dem Verzehr des ersten Wassergelees wie folgt:

• Isst Speise $1$: Seine Zufriedenheit erhöht sich um $\max(1 - 0, 4 - 0) = 4$ und wird zu $4$.
• Isst Speise $2$: Seine Zufriedenheit erhöht sich um $\max(3 - 1, 1 - 4) = 2$ und wird zu $6$.
• Isst Speise $3$: Seine Zufriedenheit erhöht sich um $\max(2 - 3, 3 - 1) = 2$ und wird zu $8$.
• Isst Speise $4$: Seine Zufriedenheit erhöht sich um $\max(3 - 2, 4 - 3) = 1$ und wird zu $9$.
• Isst Wassergelee: Seine Zufriedenheit erhöht sich um $\max(0 - 3, 0 - 4) = -3$ und wird zu $6$.