/ Vijos / 题库 /

冬瓜和信号站

冬瓜和信号站

描述

众所周知,冬瓜有一台很好的Cell Phone,功能强大,经常……咳咳,进入正题。
有一天,冬瓜的手机失去了信号,冬瓜想知道是不是信号站挂掉了……
已知有 N 个信号发射站排成一行,每个发射站i 都有不相同的高度 Hi,并能向两边(当然两端的只能向一边)同时发射信号强度值为 Vi 的信号,并且发出的信号只被两边最近的且比它高的发射站接收。
显然每个发射站发来的信号有可能被0 或 1 或 2 个其它发射站接收,它受到的能量总和是冬瓜很关心的。由于数据很多,请你帮助我们计算出接受了最多信号强度的发射站接受的信号强度总和是多少。

格式

输入格式

第1 行为一个整数N(1 ≤ N ≤ 50,000),代表信号发射站的个数。
从第2 行到第N+1 行,每行两个整数Hi 和Vi,(1 ≤ Hi ≤ 2,000,000,000, 1 ≤ Vi ≤ 10,000) 表示第i 个信号站的高和发射的信号强度值。

输出格式

输出文件为phone.out,仅一个整数,表示一个发射站能接收到的信号强度总和的最大值。

样例1

样例输入1

3
4 2
3 5
6 10

样例输出1

7

限制

每个测试点1s。

信息

ID
1803
难度
5
分类
(无)
标签
(无)
递交数
149
已通过
56
通过率
38%
上传者

相关

在下列训练计划中:

RP++分类题库