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

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

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

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

課題

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

制限

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

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

小課題

小課題 1 [10 点]

• N \leqq 16 を満たす．

小課題 2 [20 点]

• N \leqq 300 を満たす．

小課題 3 [20 点]

• N \leqq 5\,000 を満たす．

小課題 4 [50 点]

• 追加の制限はない．

入力例 1

3
2 3
11 2
4 5

出力例 1

6

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

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

この場合，美術品 1 と美術品 3 を展示するために選ぶと，次のようにして S - (A_{\mathrm{max}} - A_{\mathrm{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