1338 : 跳蚤

一只跳蚤在x正轴上跳动，对于给定x正轴上的每个点，只允许跳蚤在这些点落脚。跳蚤可以选择任意一点作为起点开始往左或往右跳，第一次跳蚤跳跃时，没有任何限制。在第二次开始跳跃之后，由于受到某种神秘力量的影响，之后跳越方向必须固定。并且，每次跳跃的距离总是大于等于上一次跳跃距离。对于给出的 $n$ 个点 $a_1，a_2，，，a_n$ ，总有一个相应的价值 $v_1，v_2，，，v_n$ 。跳蚤到达此点时可以获得相应的价值，当然，它最开始选择的点也能获取相应的价值。最后，跳蚤可自由选择在任意时间点停止跳跃。请你帮忙计算跳蚤可获得的最大总价值。

第一行一个整数 $n$ ，表示x轴上的 $n$ 个点。
第二行 $n$ 个数 $a_1，a_2，，，a_n$  为每个点的横坐标。
第三行 $n$ 个数  $v_1，v_2，，，v_n$  表示对应点的价值。

数据范围：
$1 \leq n \leq 1000，0 \leq a_i , v_i  \leq 10^6$ 

输出一个整数表示跳蚤能获取的最大价值。

11
6 4 12 2 9 1 8 5 7 10 11
5 6 11 4 11 5 4 16 14 19 12

103

Chaney丶 WIT第二届程序设计竞赛（网络赛）