题目描述

为了提高他的奖品奶牛贝西的活动能力，农夫约翰想出了一个拙劣的主意，他在贝西的每条腿上都绑了一个弹簧高跷。贝西现在可以在农场里快速地跳来跳去，但她还没有学会如何放慢速度。

为了帮助训练贝西更有控制力地跳跃，农场主约翰在他农场的一条笔直的一维路径上为她设置了一个练习课程。在路径上不同的位置，他放置了$\red{N}$个目标，贝茜应该试图降落在这些目标上 $\red{(1 <= N <= 1000)}$。目标$\red{i}$位于$\red{x(i)}$的位置，如果贝西落在它上面，值$\red{p(i)}$分。贝西从她选择的任何一个目标的位置开始，只被允许朝一个方向移动，从一个目标跳到另一个目标。每一跳必须覆盖至少与前一跳相同的距离，并且必须落在目标上。贝西每完成一个目标（）包括她开始的最初目标）都会得到表扬。请计算她可以获得的最高分数。

给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。 觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了$\red{N (1 <= N <= 1000)}$个目标点，目标点$\red{i}$在目标点$\red{x(i)，}$该点得分为$\red{p(i)}$。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点 跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。 每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。

输入格式

第$\red{1}$行:整数$\red{N}$。

第$\red{2 . .1+N:}$第$\red{i+1}$行包含$\red{x(i)}$和$\red{p(i)，}$每个都是$\red{0 \sim }$ $\red{1,000,000}$的整数。

输出格式

第一行:贝茜可以获得的最高分数。

样例

输入样例

6
5 6
1 1
10 5
7 6
4 8
8 10

输出样例

25

提示

有$\red{6}$个目标。第一个是在$\red{x=5}$的位置，值$\red{6}$点，以此类推。

贝西从位置$\red{x=4}$跳到位置$\red{x=5}$再跳到位置$\red{x=7}$再跳到位置$\red{x=10}$。