Ci sono $N + 1$ tipi di cibo in totale: $N$ tipi di cibo numerati $1, 2, \dots, N$, e la gelatina d'acqua. Per $i = 1, 2, \dots, N$, la dolcezza del cibo $i$ è $A_i$ e la sua piccantezza è $B_i$. La dolcezza della gelatina d'acqua è $0$ e la sua piccantezza è $0$.

UTPC-kun mangia prima la gelatina d'acqua, poi mangia i cibi $1, 2, \dots, N$ esattamente una volta ciascuno in qualsiasi ordine, e infine mangia di nuovo la gelatina d'acqua.

La felicità di UTPC-kun è $0$ subito dopo aver mangiato la prima gelatina d'acqua. Dopo di ciò, ogni volta che mangia un cibo, la sua felicità cambia come segue:

• Siano $a$ e $b$ la dolcezza e la piccantezza del cibo che sta mangiando attualmente, e siano $a'$ e $b'$ la dolcezza e la piccantezza del cibo che ha mangiato immediatamente prima. La sua felicità aumenta di $\max(a - a', b - b')$. (L'aumento di felicità può essere negativo.)

Trova la massima felicità finale possibile di UTPC-kun scegliendo l'ordine ottimale in cui mangiare i cibi $1, 2, \dots, N$.

Input

L'input è fornito nel seguente formato:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• Tutti i valori di input sono interi.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

Output

Stampa la risposta su una singola riga.

Esempi

Input di esempio 1

4
1 4
3 1
2 3
3 4

Output di esempio 1

6

Input di esempio 2

3
1 2
2 1
1 2

Output di esempio 2

3

Input di esempio 3

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

Output di esempio 3

18

Nota

Nel primo esempio, un ordine ottimale per mangiare i cibi è $1, 2, 3, 4$. In questo caso, la felicità di UTPC-kun cambia come segue dopo che ha finito di mangiare la prima gelatina d'acqua:

• Mangia il cibo $1$: la sua felicità aumenta di $\max(1 - 0, 4 - 0) = 4$, diventando $4$.
• Mangia il cibo $2$: la sua felicità aumenta di $\max(3 - 1, 1 - 4) = 2$, diventando $6$.
• Mangia il cibo $3$: la sua felicità aumenta di $\max(2 - 3, 3 - 1) = 2$, diventando $8$.
• Mangia il cibo $4$: la sua felicità aumenta di $\max(3 - 2, 4 - 3) = 1$, diventando $9$.
• Mangia la gelatina d'acqua: la sua felicità aumenta di $\max(0 - 3, 0 - 4) = -3$, diventando $6$.