P7667 [JOI 2018 Final] Art Exhibition / Art Exhibition

The JOI Republic will hold an art exhibition. Many artworks from all over the country will be displayed in the exhibition.

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})$.

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$.

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

#### 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](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t2-en.pdf) of The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round. Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5