Всего есть $N + 1$ видов еды: $N$ видов еды, пронумерованных $1, 2, \dots, N$, а также водяное желе. Для $i = 1, 2, \dots, N$ сладость еды $i$ равна $A_i$, а её острота равна $B_i$. Сладость водяного желе равна $0$, и его острота равна $0$.

UTPC-кун сначала съедает водяное желе, затем съедает блюда $1, 2, \dots, N$ ровно по одному разу в любом порядке, а в конце снова съедает водяное желе.

Сразу после того, как UTPC-кун съедает первое водяное желе, его счастье равно $0$. После этого каждый раз, когда он съедает какую-либо еду, его счастье меняется следующим образом:

• Пусть $a$ и $b$ — сладость и острота еды, которую он ест сейчас, а $a'$ и $b'$ — сладость и острота еды, которую он съел непосредственно перед этим. Его счастье увеличивается на $\max(a - a', b - b')$. (Увеличение счастья может быть отрицательным.)

Найдите максимально возможное итоговое счастье UTPC-куна при выборе оптимального порядка поедания блюд $1, 2, \dots, N$.

Входные данные

Входные данные даны в следующем формате:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• Все входные значения — целые числа.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

Выходные данные

Выведите ответ в единственной строке.

Примеры

Пример ввода 1

4
1 4
3 1
2 3
3 4

Пример вывода 1

6

Пример ввода 2

3
1 2
2 1
1 2

Пример вывода 2

3

Пример ввода 3

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

Пример вывода 3

18

Примечание

В первом примере один из оптимальных порядков поедания блюд — $1, 2, 3, 4$. В этом случае после первого водяного желе счастье UTPC-куна меняется следующим образом:

• Съедает блюдо $1$: его счастье увеличивается на $\max(1 - 0, 4 - 0) = 4$ и становится равным $4$.
• Съедает блюдо $2$: его счастье увеличивается на $\max(3 - 1, 1 - 4) = 2$ и становится равным $6$.
• Съедает блюдо $3$: его счастье увеличивается на $\max(2 - 3, 3 - 1) = 2$ и становится равным $8$.
• Съедает блюдо $4$: его счастье увеличивается на $\max(3 - 2, 4 - 3) = 1$ и становится равным $9$.
• Съедает водяное желе: его счастье увеличивается на $\max(0 - 3, 0 - 4) = -3$ и становится равным $6$.