该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000)，叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播，但在每个方向都只会被身高严格大于它的最近的一头奶牛听到，所以每个叫声都只会 被0，1，2头奶牛听到（这取决于它的两边有没有比它高的奶牛）。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后，Farmer John打算买一个耳罩给被残害得最厉 害的奶牛，请你帮他计算最大的总音量。

Input Format

第1行：一个正整数N. 

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

Output Format

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

3
4 2
3 5
6 10

7

Hint

队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声，于是她能听到的总音量为2+5=7．虽然她唱歌时的音量为10，但并没有奶牛可以听见她的歌声