Farmer John’s $N$ cows are standing in a very straight row and mooing. Each cow has a unique height $h_i$, and moos at some volume $v_i$. This “moo” travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by $0$, $1$ or $2$ other cows, depending on whether or not taller cows exist to the mooing cow’s right or left). The total moo volume heard by given cow is the sum of all the moo volumes $v_i$ for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, Farmer John wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.
The first line of the input contains a single integer $N \, (1 \leq N \leq 50\,000)$. $N$ lines follow, the $i$-th of them contains two space-separated integers $h_i$ and $v_i \, (1 \leq h_i \leq 2 \cdot 10^9, 1 \leq v_i \leq 10\,000)$ - the height and volume of cow $i$.
Output a single line with a single integer – the loudest moo volume heard by any single cow.
3
4 2
3 5
6 10
7
Three cows: the first one has height 4 and moos with volume 2, etc. The third cow hears both the first and second cows moo for 2 + 5 = 7. Though the third cow moos with volume 10, no one hears her.