LG#P1901. 发射站

发射站

P1901 发射站

题目描述

\hspace{15pt}某地有 nn 个能量发射站排成一行,从左往右依次编号为 1,2,…,n1, 2, \dots, n。第 ii 个发射站的高度为 hih_i,并且能够同时向左右两边发射能量值为 viv_i 的能量;位于两端的发射站只有一侧有邻居,因此只向这一侧发射。

\hspace{15pt}每个发射站发出的能量,只会被它两侧距离它最近的、高度严格大于它的发射站接收。若某一侧不存在比它高的发射站,那么这一侧发出的能量不会被任何发射站接收。

\hspace{15pt}因此,一个发射站发出的能量可能被 00 个、11 个或 22 个发射站接收。请计算出接收能量最多的发射站收到了多少能量。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦106)n \left(1 \leqq n \leqq 10^6\right) 代表发射站的数量。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 $h_i, v_i \left(1 \leqq h_i \leqq 2 \times 10^9;\ 1 \leqq v_i \leqq 10^4\right)$,分别代表第 ii 个发射站的高度和它发射的能量值。保证 h1,h2,…,hnh_1, h_2, \dots, h_n 两两不同。

输出格式

\hspace{15pt}在一行上输出一个整数,代表接收能量最多的发射站所接收到的能量值。

测试样例

3
4 2
3 5
6 10
7

样例 1 解释

\hspace{15pt}三个发射站的高度依次为 4,3,64, 3, 6,发射的能量值依次为 2,5,102, 5, 10,能量的去向如下:

∙ \hspace{23pt}\bullet\,第 11 个发射站:左侧没有发射站,向左发射的能量无人接收;向右发射的能量值为 22,被第 33 个发射站接收;

∙ \hspace{23pt}\bullet\,第 22 个发射站:向左发射的能量值为 55,被第 11 个发射站接收;向右发射的能量值为 55,被第 33 个发射站接收;

∙ \hspace{23pt}\bullet\,第 33 个发射站:两侧都没有比它高的发射站,发出的能量全部无人接收。

\hspace{15pt}于是第 11 个发射站共接收 55,第 22 个发射站共接收 00,第 33 个发射站共接收 2+5=72+5=7,接收能量的最大值为 77。

6
5 3
2 4
4 6
3 1
6 5
1 2
12

提示

\hspace{15pt}对于 40%40\% 的数据,1≦n≦5×1031 \leqq n \leqq 5 \times 10^3,1≦hi≦1051 \leqq h_i \leqq 10^5,1≦vi≦1041 \leqq v_i \leqq 10^4。

\hspace{15pt}对于 70%70\% 的数据,1≦n≦1051 \leqq n \leqq 10^5,1≦hi≦2×1091 \leqq h_i \leqq 2 \times 10^9,1≦vi≦1041 \leqq v_i \leqq 10^4。

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1061 \leqq n \leqq 10^6,1≦hi≦2×1091 \leqq h_i \leqq 2 \times 10^9,1≦vi≦1041 \leqq v_i \leqq 10^4。

\hspace{15pt}保证答案不超过 231−12^{31}-1。