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 翻译