Problem 3792. -- [noip模拟题]发射站

3792: [noip模拟题]发射站

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 17  Solved: 9
[Submit][Status][Web Board]

Description

有N个能量发射站排成一行,每个发射站i都有不相同的高度 Hi,并能向两边(当然两端的只能向一边)同时发射
能量值为Vi的能量,并且发出的能量只被两边最近的且比它高的发射站接收。显然每个发射站发来的能量有可能被
0或1或2个其它发射站接收,特别是为了安全,它受到的能量总和是我们很关心的。由于数据很多,请你帮助我们
计算出接受了最多能量的发射站接受的能量是多少。

Input

第1行:一个整数 N;
第2..N+1行:第i+1行有2个整数Hi和Vi,表示第i个发射站的高和发射的能量值。
1≤N≤800,000;1≤hi≤2,000,000,000;1≤vi≤10,000

Output

一行:一个发射站接收到的最大能量值

Sample Input

3
4 2
3 5
6 10

Sample Output

7

HINT

Source

[Submit][Status]