JOI美术展

JOI国要举办一场艺术展览。届时将展出从全国各地收集到的各种艺术品。

作为展览的候选艺术品，共有N个艺术品。这些艺术品分别被编号为1、2、...、N。每个艺术品都有一个确定的大小和价值。第i个艺术品（1 ≤ i ≤ N）的大小为Ai，价值为Bi。

在艺术展中，我们可以选择展示一个或多个这些艺术品。展览场地非常大，可以展示所有N个艺术品。但是，为了符合JOI国民的审美感，我们希望选择展示的艺术品之间的大小差异不要太大。另一方面，我们希望尽可能多地展示具有较高价值的艺术品。因此，我们决定按照以下条件选择展示的艺术品：

• 从选择的艺术品中，假设最大的艺术品的大小为Amax，最小的艺术品的大小为Amin。并设选中的艺术品的总价值为S。
• 在满足上述条件的前提下，最大化S - (Amax - Amin)。

任务

给定候选的展示艺术品数量以及每个艺术品的大小和价值，请计算S - (Amax - Amin)的最大值。

输入

从标准输入读取以下输入：

• 第1行包含一个整数N，表示候选展示艺术品的数量。
• 接下来的N行中，第i行（1 ≤ i ≤ N）包含两个整数Ai和Bi，用空格分隔。它们表示艺术品i的大小为Ai，价值为Bi。

输出

将S - (Amax - Amin)的最大值输出到标准输出的一行中。

限制

所有输入满足以下条件：

• 2 ≤ N ≤ 500,000。
• 1 ≤ Ai ≤ 1,000,000,000,000,000 ($1 \leq i \leq N$)。
• 1 ≤ Bi ≤ 1,000,000,000 ($1 \leq i \leq N$)。

子任务

子任务 1 [10 分]

• 满足N ≤ 16。

子任务 2 [20 分]

• 满足N ≤ 300。

子任务 3 [20 分]

• 满足N ≤ 5,000。

子任务 4 [50 分]

• 没有额外的限制。

输入样例 1

3
2 3
11 2
4 5

输出样例 1

6

在这个输入例子中，展示的艺术品候选有3个。每个艺术品的大小和价值如下：

• 艺术品1的大小为2，价值为3。
• 艺术品2的大小为11，价值为2。
• 艺术品3的大小为4，价值为5。

在这种情况下，选择展示艺术品1和艺术品3，可以使S - (Amax - Amin) = 6。

• 在所选择的艺术品中，最大尺寸的艺术品是艺术品3，所以Amax = 4。
• 在所选择的艺术品中，最小尺寸的艺术品是艺术品1，所以Amin = 2。
• 所选择的艺术品的价值总和为3 + 5 = 8，所以S = 8。

由于无法使S - (Amax - Amin)大于等于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