Problem Background

The Republic of JOI is hosting an art exhibition. Many artworks from all over the country will be displayed at the exhibition.

Problem Description

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

In the art exhibition, at least one artwork will be selected and displayed. Since the exhibition hall is large enough, all $N$ artworks can be displayed. However, due to the aesthetic consciousness of the people of JOI Republic, we want the selected artworks to have a not-too-large difference in size. On the other hand, we want to display many artworks with high values. We have decided to select the artworks for the exhibition according to the following rules:
- Among the selected artworks, let $A_{max}$ be the maximum size and $A_{min}$ be the minimum size. Let $S$ be the total value of the selected artworks.
- We want to maximize $S - (A_{max} - A_{min})$.

Given the number of candidate artworks for the exhibition, as well as the size and value of each artwork, please write a program to calculate 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. The next $N$ lines, the $i$-th line contains two space-separated integers $A_i$ and $B_i$, which means the size of artwork $i$ is $A_i$ and the value is $B_i$.

Output Format

The only line contains an integer, the maximum value of $S - (A_{max} - A_{min})$.

Sample Input and Output

Sample Input #1

3
2 3
11 2
4 5

Sample Output #1

6

Sample Input #2

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

Sample Output #2

7

Sample Input #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

Sample Output #3

4232545716

Notes

Data Size and Constraints

For $100\%$ of the data, $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 $2$ ($20$ points): $N \leq 300$.
• Subtask $3$ ($20$ points): $N \leq 5000$.
• Subtask $4$ ($50$ points): No additional constraints.

Sample Explanation

For Sample #1: There are $3$ artworks considered for the exhibition. The size and value of each artwork are as follows:
- Artwork $1$ has a size of $2$ and a value of $3$.
- Artwork $2$ has a size of $11$ and a value of $2$.
- Artwork $3$ has a size of $4$ and a value of $5$.

In this case, if we select artworks $1$ and $3$ for the exhibition, we have $S - (A_{max} - A_{min})$ as follows:
- Among the selected artworks, artwork $3$ has the maximum size. Thus, $A_{max} = 4$.
- Among the selected artworks, artwork $1$ has the minimum size. Thus, $A_{min} = 2$.
- The total value of the selected artworks is $3 + 5 = 8$. Thus, $S = 8$.

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

Problem Source

Derived from the T2: Art Exhibition of the 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round.
Translated and arranged by @求学的企鹅.

见题面 Input 部分

见题面 Output 部分