美術展 (Art Exhibition)

美术馆中有 $n$ 个物品，每个物品有自己的大小和价值， 我们要在其中选取若干个物品，使他们的价值总和减去其中大小最大值与大小最小值的差最大。

[problemUrl]: https://atcoder.jp/contests/joi2018ho/tasks/joi2018ho_b 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}} $) を最大化する．

標準入力から以下の入力を読み込め． - $ 1 $ 行目には，整数 $ N $ が書かれている．これは，展示される美術品の候補の個数を表す． - 続く $ N $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N $) には，$ 2 $ 個の整数 $ A_i,\ B_i $ が空白を区切りとして書かれている．これらは，美術品 $ i $ の大きさが $ A_i $，価値が $ B_i $ であることを表す．

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

3
2 3
11 2
4 5

6

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

7

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

4232545716

### 課題 展示される美術品の候補の個数と，それぞれの美術品の大きさと価値が与えられたとき，$ 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 点\] - 追加の制限はない． - - - - - - ### Sample Explanation 1 この入力例では，展示される美術品の候補が $ 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 $ を出力する． - - - - - - ### Sample Explanation 2 \- - - - - -