問題文

1, 2, \dots, N の番号がつけられた N 種類の食べ物と水ゼリーの、合計 N+1 種類の食べ物があります。i = 1, 2, \dots, N について、食べ物 i の甘さは A_i で、辛さは B_i です。また、水ゼリーの甘さは 0 で、辛さは 0 です。

UTPC 君は、はじめに水ゼリーを食べ、続いて食べ物 1, 2, \dots, N を任意の順番で 1 回ずつ食べ、最後に水ゼリーを食べます。

UTPC 君がはじめに水ゼリーを食べ終わった時点での幸福度は 0 です。これ以降、食べ物を食べる度に、UTPC 君の幸福度は次のように変化します。

• 食べる食べ物の甘さを a、辛さを b とし、その直前に食べた食べ物の甘さを a'、辛さを b' とする。このとき、UTPC 君の幸福度は \max(a - a', b - b') だけ増加する。幸福度の増加量は負であることもある。

食べ物 1, 2, \dots, N を食べる順番を工夫したときの、UTPC 君の最終的な幸福度の最大値を求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 5 \times 10^5
• 0 \leq A_i,B_i \leq 10^9

入力例 1

4
1 4
3 1
2 3
3 4

出力例 1

6

食べ物 1,2,3,4 の順番で食べればよいです。このとき、はじめに水ゼリーを食べ終わった以降の UTPC 君の幸福度の変化は以下の通りです。

• 食べ物 1 を食べる。UTPC 君の幸福度は \max(1-0,4-0) = 4 だけ増加し、4 となる。
• 食べ物 2 を食べる。UTPC 君の幸福度は \max(3-1,1-4) = 2 だけ増加し、6 となる。
• 食べ物 3 を食べる。UTPC 君の幸福度は \max(2-3,3-1) = 2 だけ増加し、8 となる。
• 食べ物 4 を食べる。UTPC 君の幸福度は \max(3-2,4-3) = 1 だけ増加し、9 となる。
• 水ゼリーを食べる。UTPC 君の幸福度は \max(0-3,0-4) = -3 だけ増加し、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