1667: 跳跃

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:37 通过:15

题目描述

小兔子国王了提高狗狗杰克的机动性,给杰克的只脚上都安装上了弹簧高跷。于是狗狗杰克可以快速的在农场里奔跑,但是她却没学会如何慢下来。

为了帮助狗狗杰克控制好速度,小兔子国王给狗狗杰克设置了一个训练踩高跷的课程。在一条直线上,小兔子国王在N个不同的位置上放置了节点,节点i的位置是Xi,并且Pi表示如果狗狗在这个节点上经过的话会得到的分数。狗狗杰克可以从任意位置开始朝一个方向行走,并且每次行走的距离要大于等于上一次行走的距离,必须保证狗狗杰克每次都走到节点上。

请帮助小兔子国王计算狗狗杰克最多可以获得的分数。

输入格式

第一行是一个正整数N,表示有N个不同的位置。
第2行到第N+1行,对于第i+1行的两个整数,表示Xi和Pi。

输出格式

输出最大的得分。

输入样例 复制

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

输出样例 复制

25

数据范围与提示

样例说明:

狗狗杰克从位置x=48分)到位置x=5(分数6)到位置x=7(分数6)到位置x=10(5分),可以得到25分。

数据范围:

1<=N<=1000,0<=Xi,Pi<=1000000

【数据规模】

对于 30%的数据: 1≤N≤100

对于 50%的数据: 1≤N≤200

对于 100%的数据:1≤N≤1,0000≤X_i,P_i≤1,000,000