某地有 N 个能量发射站排成一行,每个发射站 i 都有不相同的高度 H_i ,并能向两边(两端的发射站只能向一边)同时发射能量值为 V_i 的能量,发出的能量只被两边最近的且比它高的发射站接收。显然,每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受。
请计算出接收最多能量的发射站接收的能量是多少。
第 1 行一个整数 N 。
第 2 到 N+1 行,第 i+1 行有两个整数 H_i 和 V_i ,表示第 i 个发射站的高度和发射的能量值。
输出仅一行,表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。
3 4 2 3 5 6 10
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 。