P7667 [JOI 2018 Final] 美术展览 / Art Exhibition

JOI 共和国将举行一个艺术展。许多来自全国各地的艺术作品将在艺术展中展出。

有 $N$ 件艺术品是展览的候选作品。艺术品编号从 $1$ 到 $N$。每件艺术品都定义了两个整数：尺寸和价值。艺术品 $i$（$1 \leq i \leq N$）的尺寸为 $A_i$，艺术品 $i$ 的价值为 $B_i$。 在艺术展中，至少会选择并展示一件艺术品。由于展厅足够大，可以将 $N$ 件作品全部展示。但是，由于 JOI 共和国人的审美意识，我们希望展览选择的艺术品，使展出的艺术品尺寸之间的差异不会太大。另一方面，我们想展示许多具有高价值的艺术品。我们决定按照以下规则选择展览的艺术品： - 在选择的展览作品中，$A_{max}$ 为所选作品中最大的尺寸，$A_{min}$ 为所选作品中最小的尺寸。设 $S$ 为所选艺术品的总价值。 - 然后，我们想要最大化 $S−(A_{max}−A_{min})$。 现给定展览的艺术品候选数量，以及每件艺术品的尺寸和价值，请编写一个程序来计算 $S−(A_{max}−A_{min})$ 的最大值。

第一行包含一个整数 $N$，即展览艺术品的候选数量。接下来的 $N$ 行的第 $i$ 行包含两个空格分隔的整数 $A_i$、$B_i$，这意味着艺术品 $i$ 的尺寸是 $A_i$，价值是 $B_i$。

唯一的一行包含一个整数为 $S−(A_{max}−A_{min})$ 的最大值。

#### 数据规模与约定 对于 $100 \%$ 的数据，$2 \leq N \leq 5×10^5$，$1 \leq A_i \leq 10^{15}$（$1 \leq i \leq N$），$1 \leq B_i \leq 10^9$（$1 \leq i \leq N$）。 - Subtask $1$（$10$ points）：$N \leq 16$。 - Subtask $1$（$20$ points）：$N \leq 300$。 - Subtask $2$（$20$ points）：$N \leq 5000$。 - Subtask $3$（$50$ points）：没有额外的限制。 #### 样例说明 **对于样例 $1$**：本次展览共有 $3$ 幅作品候选。每件艺术品的尺寸和价值如下： - 艺术品 $1$ 的尺寸为 $2$，价值为 $3$。 - 艺术品 $2$ 的尺寸为 $11$，价值为 $2$。 - 艺术品 $3$ 的尺寸为 $4$，价值为 $5$。 在这种情况下，如果我们为展览选择艺术品 $1$ 和艺术品 $3$，我们有 $S−(A_{max}−A_{min})$ 如下： - 在选择的艺术品中，艺术品 $3$ 的尺寸最大。因此，$A_{max} = 4$。 - 在所选的艺术品中，艺术品 $1$ 的尺寸最小。因此，$A_{min} = 2$。 - 所选艺术品的总价值为 $3+5=8$。因此，$S=8$。 由于 $S−(A_{max}−A_{min})$ 不能大于 $7$，因此输出 $6$。 #### 题目说明： 来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T2：Art Exhibition](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t2-en.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。