Description

There are $N$ artworks that are candidates for the exhibition. The artworks are numbered from $1$ to $N$. Each artwork is defined by two integers: size and value. Artwork $i$ ($1 \leq i \leq N$) has size $A_i$, and artwork $i$ has value $B_i$.

In the exhibition, at least one artwork will be selected and displayed. Since the exhibition hall is large enough, it is possible to display all $N$ artworks. However, due to the aesthetic sense of the people of the JOI Republic, we want the selected artworks to have sizes that do not differ too much. On the other hand, we also want to display many high-value artworks. We decide to select the artworks for the exhibition according to the following rules:

• Among the selected artworks, let $A_{max}$ be the maximum size, and let $A_{min}$ be the minimum size. Let $S$ be the total value of the selected artworks.
• Then, we want to maximize $S-(A_{max}-A_{min})$.

Given the number of candidate artworks for the exhibition, and the size and value of each artwork, write a program to compute the maximum value of $S-(A_{max}-A_{min})$.

Input Format

The first line contains an integer $N$, the number of candidate artworks for the exhibition. Each of the next $N$ lines, the $i$-th line contains two space-separated integers $A_i$ and $B_i$, meaning that artwork $i$ has size $A_i$ and value $B_i$.

Output Format

The only line contains one integer, the maximum value of $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

Hint

Constraints

For $100\%$ of the testdata, $2 \leq N \leq 5 \times 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): No additional constraints.

Sample Explanation

For Sample $1$: There are $3$ candidate artworks in this exhibition. The size and value of each artwork are as follows:

• Artwork $1$ has size $2$ and value $3$.
• Artwork $2$ has size $11$ and value $2$.
• Artwork $3$ has size $4$ and value $5$.

In this case, if we choose artwork $1$ and artwork $3$ for the exhibition, we have $S-(A_{max}-A_{min})$ as follows:

• Among the selected artworks, artwork $3$ has the largest size. Therefore, $A_{max}=4$.
• Among the selected artworks, artwork $1$ has the smallest size. Therefore, $A_{min}=2$.
• The total value of the selected artworks is $3+5=8$. Therefore, $S=8$.

Since $S-(A_{max}-A_{min})$ cannot be greater than $7$, output $6$.

Problem Notes

This problem is from T2: Art Exhibition of The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5