← 返回题目列表

AtCoder · joi2018ho_b

B. 艺术展

中文机器翻译题面 查看原题

配点: 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