CF392E.Deleting Substrings

SmallR likes a game called "Deleting Substrings". In the game you are given a sequence of integers w, you can modify the sequence and get points. The only type of modification you can perform is (unexpected, right?) deleting substrings. More formally, you can choose several contiguous elements of w and delete them from the sequence. Let's denote the sequence of chosen elements as w__l, w__l + 1, ..., w__r. They must meet the conditions:

• the equality |w__i - w__i + 1| = 1 must hold for all i (l ≤ i < r);
• the inequality 2·w__i - w__i + 1 - w__i - 1 ≥ 0 must hold for all i (l < i < r).

After deleting the chosen substring of w, you gain v__r - l + 1 points. You can perform the described operation again and again while proper substrings exist. Also you can end the game at any time. Your task is to calculate the maximum total score you can get in the game.

SmallR 喜欢一个名为“删除子串”的游戏。在该游戏中，你将获得一个整数序列 $ w $，你可以对序列进行修改并获得分数。唯一允许的修改操作（出人意料，对吧？）就是删除子串。更准确地说，你可以选择 $ w $ 中若干个连续的元素并将它们从序列中删除。记所选元素构成的子序列为 $ w_l,,w_{l+1},,...,,w_r $。该子序列必须满足以下条件：

• 对所有 $ i $（其中 $ l \le i < r $），均有 $ |w_i - w_{i+1}| = 1 $；
• 对所有 $ i $（其中 $ l < i < r $），均有 $ 2\cdot w_i - w_{i+1} - w_{i-1} \ge 0 $。

在删除该子串后，你将获得 $ v_{r-l+1} $ 分。只要仍存在满足上述条件的子串，你就可以重复执行上述操作；当然，你也可以在任意时刻结束游戏。你的任务是计算在游戏中所能获得的最大总分。

The first line contains a single integer n (1 ≤ n ≤ 400) — the initial length of w. The second line contains n integers _v_1, _v_2, ..., v__n (0 ≤ |v__i| ≤ 2000) — the costs of operations. The next line contains n integers _w_1, _w_2, ..., w__n (1 ≤ w__i ≤ 109) — the initial w.

第一行包含一个整数 $n$（$1 \leq n \leq 400$）—— 表示 $w$ 的初始长度。
第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$（$0 \leq |v_i| \leq 2000$）—— 表示各操作的代价。
接下来的一行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \leq w_i \leq 10^9$）—— 表示 $w$ 的初始值。

Print a single integer — the maximum total score you can get.

输出一个整数——你能获得的最高总分。