配点: 100 点
JOI国将举办艺术展。此次艺术展将展出来自全国各地的各类艺术作品。
作为参展作品的候选者,N 艺术作品集。这些艺术作品包括 它的编号为 1, 2, \ldots, N 。每件艺术品都有一个固定的价值,称为尺寸和价值。艺术品 i (1 \leqq i \leqq N) 的大小是 A_i,值为 B_i 。
这些艺术作品将在艺术展上展出。 1 选择并显示至少 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