Time Limit: 1 sec / Memory Limit: 256 MB
配点: 100 点
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}}) の最大値を求めよ.
入力
標準入力から以下の入力を読み込め.
- 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 行で出力せよ.
制限
すべての入力データは以下の条件を満たす.
- 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