P3089 [USACO13NOV] Pogo-Cow S

FJ 给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。 为了训练贝西更好地控制跳跃，FJ 在农场的一条笔直一维路径上设置了一个练习场。他在路径的不同位置放置了 $N$ 个目标点 $(1 \le N \le 1000)$，贝西需要尝试落在这些点上。目标点 $i$ 的位置坐标为 $x_i$，如果贝西落在上面，就能获得 $p_i$ 分。 贝西可以从任意一个目标点开始起跳，并且只能朝一个方向移动（向左或向右），从一个目标点跳到另一个目标点。每次跳跃的距离必须大于等于上一次跳跃的距离，而且必须落在目标点上。 每跳到一个目标点，贝西可以拿到该点的得分。请计算他的最大可能得分。

- 第一行，一个整数 $N$。 - 第二行到第 $N+1$ 行，第 $i+1$ 行包含两个整数 $x_i$ 和 $p_i$，其中 $0 \le x_i, p_i \le 10^6$。

- 一行一个整数，表示贝西的最大得分。

有 $6$ 个目标点。第一个目标点位于位置 $x=5$，价值 $6$ 分，依此类推。 贝西从位置 $x=4$（$8$ 分）跳到位置 $x=5$（$6$ 分），再跳到位置 $x=7$（$6$ 分），最后跳到位置 $x=10$（$5$ 分）。共计 $25$ 分。 ### 数据规模与约定 - $1 \le N \le 1000$ - $0 \le x_i, p_i \le 10^6$