题目背景

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})$ 的最大值。

3
2 3
11 2
4 5

6

6
4 1
1 5
10 3
9 1
4 2
5 3

7

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

4232545716

提示

数据规模与约定

对于 $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。
由 @求学的企鹅 翻译整理。