Барлығы $N + 1$ тағам түрі бар: $1, 2, \dots, N$ сандарымен нөмірленген $N$ тағам түрі және су желесі. $i = 1, 2, \dots, N$ үшін $i$-ші тағамның тәттілігі $A_i$, ал ащылығы $B_i$. Су желесінің тәттілігі $0$, ал ащылығы $0$.

UTPC-kun алдымен су желесін жейді, содан кейін $1, 2, \dots, N$ тағамдарының әрқайсысын кез келген ретпен дәл бір реттен жейді, ал соңында қайтадан су желесін жейді.

Бірінші су желесін жегеннен кейін бірден UTPC-kun-ның бақыт деңгейі $0$-ге тең болады. Одан кейін ол әр тағамды жеген сайын оның бақыт деңгейі келесідей өзгереді:

• $a$ мен $b$ — оның қазір жеп жатқан тағамының тәттілігі мен ащылығы болсын, ал $a'$ пен $b'$ — дәл оның алдында жеген тағамының тәттілігі мен ащылығы болсын. Оның бақыт деңгейі $\max(a - a', b - b')$ шамасына артады. (Бақыт деңгейінің өсімі теріс болуы да мүмкін.)

$1, 2, \dots, N$ тағамдарын жеудің оңтайлы ретін таңдау арқылы UTPC-kun-ның мүмкін болатын ең үлкен соңғы бақыт деңгейін табыңыз.

Кіріс деректер

Кіріс деректер келесі форматта беріледі:

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-kun-ның бақыт деңгейі келесідей өзгереді:

• $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$ болады.