美術展(Art Exhibition)

JOI 国で美術展が行われることになった．美術展では，国中から集まった様々な美術品が展示される予定である．

展示される美術品の候補として，N 点の美術品が集まった．これらの美術品には1, 2, ..., N の番号が付けられている．それぞれの美術品には大きさと価値と呼ばれる値が定まっている．美術品i (1 \leq i \leq N) の大きさはA_i，価値はB_i である．

美術展では，これらの美術品のうちから1 点以上を選んで展示する．美術展の会場は十分に広く，N 点の美術品すべてを展示することも可能である．しかし，JOI 国の人々の美的感覚のため，美術品の間で大きさの差があまり大きくならないように展示する美術品を選びたい．一方，できるだけ価値の大きい美術品を多く展示したい．そのため，次の条件を満たすように展示する美術品を選ぶことにした：

• 選んだ美術品の中で，大きさが最大のものの大きさをA_{max}，最小のものの大きさをA_{min} とする．また，選んだ美術品の価値の総和をS とする．
• このとき，S - (A_{max} - A_{min}) を最大化する．

課題

展示される美術品の候補の個数と，それぞれの美術品の大きさと価値が与えられたとき，S - (A_{max} - A_{min})の最大値を求めよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には，整数N が書かれている．これは，展示される美術品の候補の個数を表す．
• 続くN 行のうちのi 行目(1 \leq i \leq N) には，2 個の整数A_i, B_i が空白を区切りとして書かれている．これらは，美術品i の大きさがA_i，価値がB_i であることを表す．

出力

標準出力に，S - (A_{max} - A_{min}) の最大値を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leq N \leq 500 000．
• 1 \leq A_i \leq 1 000 000 000 000 000 = 10^{15} (1 \leq i \leq N)．
• 1 \leq B_i \leq 1 000 000 000 (1 \leq i \leq N)．

入出力例

入力例1

3
2 3
11 2
4 5

出力例1

6

この入力例では，展示される美術品の候補が3 点ある．それぞれの美術品の大きさ，価値は次の通りである．

• 美術品1 の大きさは2，価値は3 である．
• 美術品2 の大きさは11，価値は2 である．
• 美術品3 の大きさは4，価値は5 である．

この場合，美術品1 と美術品3 を展示するために選ぶと，次のようにしてS - (A_{max} - A_{min}) = 6 となる．

• 選んだ中で大きさが最大の美術品は，美術品3 である．よって，A_{max} = 4 である．
• 選んだ中で大きさが最小の美術品は，美術品1 である．よって，A_{min} = 2 である．
• 選んだ美術品の価値の総和は3 + 5 = 8 であるから，S = 8 である．

S - (A_{max} - A_{min}) を7 以上にすることは不可能なので，6 を出力する．

入力例2

6
4 1
1 5
10 3
9 1
4 2
5 3

出力例2

7

入力例3

15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562

出力例3

4232545716

情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』

---