Maximizing Contribution in the LoGu Contest System

A new contribution system has been implemented on LoGu! In a monthly contest, there are ( n ) participants. Each participant has a unique rating ( r_i ) and an associated contribution value ( c_i ). Before the contest, let the ranking of the participants by rating (in descending order) be ( a = (a_1, a_2, \dots, a_n) ), which is a permutation of ({1,2,\dots,n}) with ( a_i ) being the rank of the ( i )-th participant in this order. After the contest the final results form another permutation ( b = (b_1, b_2, \dots, b_n) ) (i.e. the contest ranking, with no ties). Then each participant performs the following action:

• If ( a_i = b_i ), nothing happens.
• If ( a_i > b_i ) (i.e. the participant did better than expected), their rating increases; consequently, they give a like to the problem setter which increases the setter’s contribution by ( c_i ) (note that ( c_i ) may be negative, resulting in a decrease).
• If ( a_i < b_i ) (i.e. the participant did worse than expected), their rating decreases; consequently, they give a dislike to the problem setter which decreases the setter’s contribution by ( c_i ) (if ( c_i ) is negative, the contribution increases).

As the only problem setter, you start with a contribution of (0). Knowing that the pre‐contest ranking ( a ) is fixed (by ratings) and that the contest ranking ( b ) can be any permutation of ({1,2,\dots,n}), you wonder: What is the maximum possible final contribution you can achieve over all possible permutations ( b )?

A key observation is that for each participant the effect is determined by whether their final rank ( b_i ) is less than, equal to, or greater than their original rank ( a_i ). Formally, define the effect for the ( i )-th participant as follows:

[ f(i) = \begin{cases} c_i, & \text{if } b_i < a_i,\[6mm] 0, & \text{if } b_i = a_i,\[6mm] -c_i, & \text{if } b_i > a_i. \end{cases} ]

Thus, the total contribution is ( \sum_{i=1}^{n} f(i) ). However, not every assignment of ( b_i ) is allowed. In fact, the permutation ( b ) must be chosen so that for each participant the chosen option is feasible. Notice that if we denote the participants sorted by rating in descending order (so that the ( i )-th participant has rating rank ( a_i = i )), then a participant ( i ) can receive a like (i.e. choose an option corresponding to ( b_i < i )) only if there is an available rank in ( {1,2,\dots,i-1} ); similarly, a dislike (i.e. ( b_i > i )) is possible only if ( i < n ) (since ( b_i ) must be at most ( n )). That is, for the best participant (( i=1 )) the like option is impossible, and for the worst participant (( i=n )) the dislike option is impossible.

Your task is to choose a permutation ( b ) satisfying the feasibility conditions (and the inherent constraint that ( b ) is a permutation of ({1,2,\dots,n})) so that the final contribution [ \text{Total} = \sum_{i=1}^{n} f(i) ] is maximized. It turns out that this problem can be reformulated as selecting, for each participant, one of three actions:

• Action L (like): can be chosen if ( i \ge 2 ) (i.e. not for the best participant) and gives a reward of ( c_i ).
• Action E (equal): always allowed and gives ( 0 ) effect.
• Action D (dislike): can be chosen if ( i \le n-1 ) (i.e. not for the worst participant) and gives a reward of ( -c_i ).

However, there is an additional global constraint: when assigning the final ranks, the numbers chosen for the participants must form a permutation of ({1,2,\dots,n}). It can be shown that if we assign the minimum possible deviation for each participant in an action, then the overall feasibility condition is equivalent to requiring that the number of participants selecting action L equals the number selecting action D.

Determine the maximum total contribution achievable.

inputFormat

The first line contains an integer \( n \) (\( 1 \le n \le 10^5 \)), representing the number of participants.

Each of the next \( n \) lines contains two integers \( r_i \) and \( c_i \) (\( -10^9 \le c_i \le 10^9 \)); \( r_i \) is the rating and \( c_i \) the contribution value of the \( i \)-th participant. It is guaranteed that all \( r_i \) are distinct.

outputFormat

Output a single integer: the maximum final contribution that can be achieved.

sample

3
1000 5
900 2
800 -3

0

</p>