A2772. 奶牛贝西
编程题
提高+/省选-
知识点
题目描述
FJ给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。
FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。
每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。
FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。
每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。
输入格式
* 第 1 行：整数 N。
* 第 2..1+N 行：第 i+1 行包含 x（i） 和 p（i），每个都是 0..1,000,000 范围内的整数。
* 第 2..1+N 行：第 i+1 行包含 x（i） 和 p（i），每个都是 0..1,000,000 范围内的整数。
输出格式
* 第 1 行：Bessie 可以获得的最大积分数。
输入输出样例
输入 #1
6 5 6 1 1 10 5 7 6 4 8 8 10
输出 #1
25
说明/提示
有 6 个目标。第一个位于位置 x=5，值 6 点，依此类推。
Bessie 从位置 x=4（8 点）跳到位置 x=5（6 点）到位置 x=7（6 点）到位置 x=10（5 点）。
Bessie 从位置 x=4（8 点）跳到位置 x=5（6 点）到位置 x=7（6 点）到位置 x=10（5 点）。