JOI 共和国将举办一场艺术展览。全国各地的许多艺术品都将在展览中展出。

共有 $N$ 件艺术品作为展览的候选作品。艺术品编号为 $1$ 到 $N$。每件艺术品都有两个整数属性：尺寸和价值。艺术品 $i$ ($1 \le i \le N$) 的尺寸为 $A_i$，价值为 $B_i$。

在艺术展览中，至少会选择并展出一件艺术品。由于展览大厅足够大，展出全部 $N$ 件艺术品也是可能的。然而，出于 JOI 共和国人民的审美需求，我们希望选择展出的艺术品，使得所选艺术品尺寸之间的差异不会太大。另一方面，我们希望展出许多价值较高的艺术品。我们决定按照以下规则选择参展艺术品：

• 在所选的参展艺术品中，设 $A_{\max}$ 为所选艺术品中的最大尺寸，$A_{\min}$ 为所选艺术品中的最小尺寸。设 $S$ 为所选艺术品的总价值。
• 然后，我们希望最大化 $S - (A_{\max} - A_{\min})$。

题目描述

给定展览的候选艺术品数量，以及每件艺术品的尺寸和价值，编写一个程序来计算 $S - (A_{\max} - A_{\min})$ 的最大值。

输入格式

从标准输入读取以下数据。

• 第一行包含一个整数 $N$，表示展览的候选艺术品数量。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含两个空格分隔的整数 $A_i, B_i$。这意味着艺术品 $i$ 的尺寸为 $A_i$，价值为 $B_i$。

输出格式

向标准输出打印一行。输出应包含 $S - (A_{\max} - A_{\min})$ 的最大值。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 500\,000$。
• $1 \le A_i \le 1\,000\,000\,000\,000\,000 = 10^{15}$ ($1 \le i \le N$)。
• $1 \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$)。

子任务

子任务 1 [10 分]

• $N \le 16$。

子任务 2 [20 分]

• $N \le 300$。

子任务 3 [20 分]

• $N \le 5000$。

子任务 4 [50 分]

• 无附加限制。

样例

输入 1

3
2 3
11 2
4 5

输出 1

6

说明 1

在此样例中，有 3 件候选艺术品。每件艺术品的尺寸和价值如下： 艺术品 1 的尺寸为 2，价值为 3。 艺术品 2 的尺寸为 11，价值为 2。 * 艺术品 3 的尺寸为 4，价值为 5。

在这种情况下，如果我们选择艺术品 1 和艺术品 3 参展，我们得到 $S - (A_{\max} - A_{\min}) = 6$，计算方式如下： 在所选艺术品中，艺术品 3 的尺寸最大。因此，$A_{\max} = 4$。 在所选艺术品中，艺术品 1 的尺寸最小。因此，$A_{\min} = 2$。 * 所选艺术品的总价值为 $3 + 5 = 8$。因此，$S = 8$。 由于 $S - (A_{\max} - A_{\min})$ 不可能大于 7，输出 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