Problem Description

An art exhibition is going to be held in the Kingdom of JOI. The exhibition is planned to showcase various artworks collected from all over the country.

As candidates for the exhibition, $N$ artworks have been gathered. These artworks are numbered from $1$ to $N$. Each artwork has a specified size and value. The size of artwork $i$ ($1 \leq i \leq N$) is $A_i$, and its value is $B_i$.

At the art exhibition, one or more of these artworks will be selected for display. The exhibition venue is spacious enough to accommodate all $N$ artworks if necessary. However, due to the aesthetic sensibilities of the people of JOI, they want to select artworks such that the difference in size between them is not too large. At the same time, they want to display as many high-value artworks as possible. Therefore, they decided to select the artworks to be displayed to maximize the following expression:

• Let $A_{\mathrm{max}}$ be the size of the largest artwork chosen, and $A_{\mathrm{min}}$ be the size of the smallest artwork chosen. Also, let $S$ be the total value of the chosen artworks.
• The goal is to maximize $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$.

Input Format

Read the following input from the standard input:

• The first line contains an integer $N$, which represents the number of candidate artworks for the exhibition.
• The next $N$ lines contain two integers each, $A_i$ and $B_i$, separated by a space. These represent the size and value of artwork $i$ ($1 \leq i \leq N$), respectively.

Output Format

Output the maximum value of $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$ on a single line to the standard output.

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/Hints

Task

Given the number of candidate artworks for the exhibition and the size and value of each artwork, find the maximum value of $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [10 points]

• $N \leq 16$.

Subtask 2 [20 points]

• $N \leq 300$.

Subtask 3 [20 points]

• $N \leq 5,000$.

Subtask 4 [50 points]

• No additional constraints.

Sample Explanation 1

In this input example, there are $3$ candidate artworks for the exhibition. The sizes and values of the artworks are as follows:
- The size of artwork $1$ is $2$, and its value is $3$.
- The size of artwork $2$ is $11$, and its value is $2$.
- The size of artwork $3$ is $4$, and its value is $5$.

In this case, selecting artworks $1$ and $3$ for display results in $S - (A_{\mathrm{max}} - A_{\mathrm{min}}) = 6$ as follows:
- The largest artwork chosen is artwork $3$, so $A_{\mathrm{max}} = 4$.
- The smallest artwork chosen is artwork $1$, so $A_{\mathrm{min}} = 2$.
- The total value of the chosen artworks is $3 + 5 = 8$, so $S = 8$.

It is impossible to make $S - (A_{\mathrm{max}} - A_{\mathrm{min}})$ greater than $7$, so output $6$.

Sample Explanation 2

见题面 Input 部分

见题面 Output 部分