P1901 Transmitter Stations

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.

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 a single line containing the maximum energy received by any station. The answer fits in a 32-bit signed integer.

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