4360: 「JOI 2018 Final」美术展览
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
JOI 国将举行美术展，在美术展中将展出来自全国各地的各种美术品。
现在有 $N$ 件候选美术品，编号为 $1$ 至 $N$。每件艺术品有描述其尺寸与价值的两个整数，第 $i$ 件艺术品的尺寸为 $A_i$，其价值为 $B_i$。
美术展至少有一件美术品被选中并展示，并且举办美术展的展览馆足够大，所以展出所有的 $N$ 件美术品也是可行的。为了符合 JOI 国人民的审美，我们想使得参展的美术品之间的尺寸之差不能太大。并且，我们想使得参展的美术品价值之和尽量大。因此，我们决定按照以下方式选定参展的美术品：
在参展美术品中，令 $A_\max$ 为所选美术品中最大的尺寸，$A_\min$ 为所选美术品中最小的尺寸。令 $S$ 为所有参展美术品的总价值之和。给出候选美术品的数量以及其尺寸与价值，求 $S-(A_\max-A_\min)$ 的最大值。
输入
从标准输入中读取数据。
第一行包括一个整数 $N$，表示有 $N$ 件候选美术品。
接下来 $N$ 行，第 $i+1$ 行给出两个整数 $A_i, B_i$，表示第 $i$ 件美术品的尺寸与价值。
输出
输出数据到标准输出中。
输出一行一个整数，表示 $S-(A_\max-A_\min)$ 的最大值。
样例输入 复制
3
2 3
11 2
4 5样例输出 复制
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
数据范围：|Subtask #|1|2|3|4| |-|-|-|-|-| |分值|10|20|20|50| |$N$|$N\le 16$|$N \le 300$|$N \le 5000$|$N \le 5\times 10^5$| 对于所有输入数据，有 $2≤N≤5\times 10^5$，$1≤A_i≤10^{15}$ $(1≤i≤N)$，$1≤B_i≤10^9$ $(1≤i≤N)$。