#P1243. 跳格子1

跳格子1

题目描述

贝西在一条直线的一维线路上进行练习,他在不同的目标点放置了N (1 <= N <= 100)个目标点,目标点i在目标点x(i),该点得分为p(i)。贝西开始时可以选择站在一个目标点上,只允许朝一个方向跳跃,从一目标点跳到另外一个目标点,每次跳跃的距离至少和上一次跳跃的距离相等,并且必须跳到一个目标点。 每跳到一个目标点,贝西可以拿到该点的得分,请计算他的最大可能得分。

输入格式

* 第1行一个整数N

* 第2行到第N行: 每行2个整数 x(i)和 p(i), 数据范围是0到1,000,000.

输出格式

* 一个整数表示贝西的最大可能得分。

样例 #1

样例输入 #1

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

样例输出 #1

25