#P3315. [Usaco2013 Nov]Pogo-Cow
[Usaco2013 Nov]Pogo-Cow
题目描述
农夫约翰给贝茜的腿装上了弹簧,让她能跳着移动,但贝茜还没有学会减速。为了练习,他在一条直线上的不同位置放置了 个靶点。靶点 的位置为 ,踩到它可获得 分。
贝茜任选一个靶点出发,选定向左或向右后始终沿该方向跳。每一跳都必须落在一个靶点上,且从第二跳开始,每一跳的长度都不得小于上一跳。
起点和每次落到的靶点都计分。贝茜可以停在任一靶点。求她最多能得到多少分。
输入格式
从标准输入读取。第一行是整数 。接下来 行,每行两个整数 ,表示一个靶点的位置和分值。
输出格式
向标准输出写入。输出一行一个整数,表示最高总得分。
样例 1
6
5 6
1 1
10 5
7 6
4 8
8 10
25
样例说明
贝茜可以从位置 出发,依次跳到 ,跳跃长度为 。她得到 分。
数据范围
,,各靶点位置互不相同。