#2498. 奶牛的歌声

奶牛的歌声

题目描述

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

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

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

输入格式

1\red{1}行:一个正整数N.\red{N.}

2\red{2}N+1\red{N+1}行:

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

输出格式

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

样例

输入样例

3
4 2
3 5
6 10

输出样例

7

提示

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

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

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

统计

相关

在下列比赛中:

数据结构