AT_joi2018ho_b 美術展 (Art Exhibition)

[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 $ 行で出力せよ． - - - - - -

### 課題 展示される美術品の候補の個数と，それぞれの美術品の大きさと価値が与えられたとき，$ 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 \- - - - - -