#P2348. 「JOI 2018 Final」美术展览

「JOI 2018 Final」美术展览

题目描述

JOI 国将举行美术展,在美术展中将展出来自全国各地的各种美术品。

现在有 NN 件候选美术品,编号为 11NN。每件艺术品有描述其尺寸与价值的两个整数,第 ii 件艺术品的尺寸为 AiA_i,其价值为 BiB_i

美术展至少有一件美术品被选中并展示,并且举办美术展的展览馆足够大,所以展出所有的 NN 件美术品也是可行的。为了符合 JOI 国人民的审美,我们想使得参展的美术品之间的尺寸之差不能太大。并且,我们想使得参展的美术品价值之和尽量大。因此,我们决定按照以下方式选定参展的美术品:

在参展美术品中,令 A_\max 为所选美术品中最大的尺寸,A_\min 为所选美术品中最小的尺寸。令 SS 为所有参展美术品的总价值之和。给出候选美术品的数量以及其尺寸与价值,求 S-(A_\max-A_\min) 的最大值。

输入格式

从标准输入中读取数据。

第一行包括一个整数 NN,表示有 NN 件候选美术品。

接下来 NN 行,第 i+1i+1 行给出两个整数 Ai,BiA_i, B_i,表示第 ii 件美术品的尺寸与价值。

输出格式

输出数据到标准输出中。

输出一行一个整数,表示 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

数据范围与提示

Subtask # 1 2 3 4
分值 10 20 50
NN N16N\le 16 N300N \le 300 N5000N \le 5000 N5×105N \le 5\times 10^5

对于所有输入数据,有 2N5×1052≤N≤5\times 10^51Ai10151≤A_i≤10^{15} (1iN)(1≤i≤N)1Bi1091≤B_i≤10^9 (1iN)(1≤i≤N)