奶牛的歌声
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
Farmer John的 N 头奶牛整齐地站成一列“嚎叫”。第 i 头奶牛的高度为 h,叫的音量为 v。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个奶牛的叫声都只会被 0,1,2 头奶牛听到(这取决于它的两边有没有比它高的奶牛)。一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉害的奶牛,请你帮他找出哪头奶牛听到的总音量最大,输出这个最大值。
输入
第一行: 一个整数 N.
接下来 N 行: 每行两个整数 ,分别代表站在队伍中第 i 个位置的奶牛的身高以及她唱歌时的音量.
输出
一个整数,表示能听到的最高的总音量.
样例输入
3
4 2
3 5
6 10
样例输出
7
样例解释
队伍中的第 3 头奶牛可以听到第 1 头和第 2 头奶牛的歌声,于是她能听到的总音量为 2+5=7.虽然她唱歌时的音量为 10,但并没有奶牛可以听见她的歌声.
数据范围