题目描述

一条直线上均匀分布着 $N$ 个能量中继站，编号从 $1$ 到 $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$。