AT_joi2018ho_b 美術展 (Art Exhibition)

在 JOI 国即将举办一场美术展。美术展计划展出来自全国各地的各种美术品。 作为展出候选，共收集了 $N$ 件美术品。这些美术品编号为 $1, 2, \ldots, N$。每件美术品都有一个称为“大きさ”（大小）和“価値”（价值）的属性。第 $i$ 件美术品（$1 \leq i \leq N$）的大小为 $A_i$，价值为 $B_i$。 在美术展中，将从这些美术品中选择至少 $1$ 件进行展出。展览会场足够大，可以展出全部 $N$ 件美术品。然而，考虑到 JOI 国人民的审美观，希望所选美术品的大小差异不要太大。同时，也希望尽可能多地展出高价值的美术品。因此，决定按照以下条件选择展出美术品： - 在所选美术品中，最大大小记为 $A_{\mathrm{max}}$，最小大小记为 $A_{\mathrm{min}}$。所选美术品的价值总和记为 $S$。 - 选择使 $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$ 最大的方案。

从标准输入读取以下内容。 - 第 $1$ 行包含一个整数 $N$，表示候选美术品的数量。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含两个用空格分隔的整数 $A_i, B_i$，分别表示第 $i$ 件美术品的大小和价值。

输出 $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$ 的最大值。

## 问题 给定候选美术品的数量，以及每件美术品的大小和价值，求 $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$ 的最大值。 ## 限制 所有输入数据满足以下条件： - $2 \leq N \leq 500\,000$。 - $1 \leq A_i \leq 1\,000\,000\,000\,000\,000 = 10^{15}$（$1 \leq i \leq N$）。 - $1 \leq B_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 ## 子任务 ### 子任务 1 [10 分] - $N \leq 16$。 ### 子任务 2 [20 分] - $N \leq 300$。 ### 子任务 3 [20 分] - $N \leq 5\,000$。 ### 子任务 4 [50 分] - 无额外限制。 ## 样例解释 1 在此输入样例中，有 $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 - - - - - - 由 ChatGPT 4.1 翻译