#P3315. [Usaco2013 Nov]Pogo-Cow

    ID: 2503 传统题 1000ms 512MiB 尝试: 420 已通过: 141 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划线性 DP排序与序列处理前后缀最值模拟与实现技巧增量维护坐标变换CF1800单调队列/单调栈优化

[Usaco2013 Nov]Pogo-Cow

题目描述

农夫约翰给贝茜的腿装上了弹簧,让她能跳着移动,但贝茜还没有学会减速。为了练习,他在一条直线上的不同位置放置了 NN 个靶点。靶点 ii 的位置为 xix_i,踩到它可获得 pip_i 分。

贝茜任选一个靶点出发,选定向左或向右后始终沿该方向跳。每一跳都必须落在一个靶点上,且从第二跳开始,每一跳的长度都不得小于上一跳。

起点和每次落到的靶点都计分。贝茜可以停在任一靶点。求她最多能得到多少分。

输入格式

从标准输入读取。第一行是整数 NN。接下来 NN 行,每行两个整数 xi,pix_i,p_i,表示一个靶点的位置和分值。

输出格式

向标准输出写入。输出一行一个整数,表示最高总得分。

样例 1

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

样例说明

贝茜可以从位置 44 出发,依次跳到 5,7,105,7,10,跳跃长度为 1,2,31,2,3。她得到 8+6+6+5=258+6+6+5=25 分。

数据范围

1≤N≤10001\le N\le1000,0≤xi,pi≤1060\le x_i,p_i\le10^6,各靶点位置互不相同。