题目描述

$\red{Farmer John}$的$\red{N(1<=N<=50,000)}$头奶牛整齐地站成一列"嚎叫"。每头奶牛有一个确定的高度$\red{h(1<=h<=2000000000)，}$叫的音量为$\red{v (1<=v<=10000)}$。

每头奶牛的叫声向两端传播，但在每个方向都只会被身高严格大于它的最近的一头奶牛听到，所以每个叫声都只会 被$\red{0，}$$\red{1，}$$\red{2}$头奶牛听到（这取决于它的 两边有没有比它高的奶牛）。

一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后，$\red{Farmer John}$打算买一个耳罩给被残害得最厉 害的奶牛，请你帮他计算最大的总音 量。

输入格式

第$\red{1}$行：一个正整数$\red{N.}$

第$\red{2}$到$\red{N+1}$行：

每行包括$\red{2}$个用空格隔开的整数，分别代表站在队伍中第$\red{i}$个位置的奶牛的身高以及她唱歌时的音量．

输出格式

队伍中的奶牛所能听到的最高的总音量．

样例

输入样例

3
4 2
3 5
6 10

输出样例

7

提示

输入详细信息： 三头牛：第一头牛身高$\red{4，}$第二卷有$\red{moos，}$等等。

队伍中的第$\red{3}$头奶牛可以听到第$\red{1}$头和第$\red{2}$头奶牛的歌声，于是她能听到的总音量为$\red{2+5=7}$．

虽然她唱歌时的音量为$\red{10，}$但并没有奶牛可 以听见她的歌声．