发射站

题目描述

某地有 $N$ 个能量发射站排成一行,每个发射站 $i$ 都有不相同的高度 $H_i$,并能向两边(两端的发射站只能向一边)同时发射能量值为 $V_i$ 的能量,发出的能量只被两边**最近的且比它高**的发射站接收。显然,每个发射站发来的能量有可能被 $0$ 或 $1$ 或 $2$ 个其他发射站所接受。 请计算出接收最多能量的发射站接收的能量是多少。

输入输出格式

输入格式


第 $1$ 行一个整数 $N$。 第 $2$ 到 $N+1$ 行,第 $i+1$ 行有两个整数 $H_i$ 和 $V_i$,表示第 $i$ 个发射站的高度和发射的能量值。

输出格式


输出仅一行,表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。

输入输出样例

输入样例 #1

3
4 2 
3 5 
6 10

输出样例 #1

7

说明

对于 $40\%$ 的数据,$1\le N\le 5000,1\le H_i\le 10^5,1\le V_i\le 10^4$。 对于 $70\%$ 的数据,$1\le N\le 10^5,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。 对于 $100\%$ 的数据,$1\le N\le 10^6,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。