Description

There are $N$ energy transmitter stations arranged in a line. Each station $i$ has a pairwise distinct height $H_i$ and can simultaneously emit energy of value $V_i$ to both sides (stations at the ends can emit only to one side). The emitted energy is received only by the nearest and taller station on each side. Clearly, the energy from a station may be received by $0$, $1$, or $2$ other stations.

Please compute the amount of energy received by the station that receives the most energy.

Input Format

The first line contains an integer $N$.

Lines $2$ through $N+1$: line $i+1$ contains two integers $H_i$ and $V_i$, denoting the height of the $i$-th station and the value of the energy it emits.

Output Format

Output a single line containing the maximum energy received by any station. The answer fits in a 32-bit signed integer.

3
4 2 
3 5 
6 10

7

Hint

For $40\%$ of the testdata, $1\le N\le 5000, 1\le H_i\le 10^5, 1\le V_i\le 10^4$.

For $70\%$ of the testdata, $1\le N\le 10^5, 1\le H_i\le 2\times 10^9, 1\le V_i\le 10^4$.

For $100\%$ of the testdata, $1\le N\le 10^6, 1\le H_i\le 2\times 10^9, 1\le V_i\le 10^4$.

Translated by ChatGPT 5