SmallR 喜欢一个叫做“删除子串”的游戏。游戏中给你一个整数序列w,你可以修改该序列并获得分数。您可以执行的唯一修改类型是(意外的,对吧?)删除子字符串。更正式地说,您可以选择 w 的几个连续元素并将它们从序列中删除。我们将所选元素的序列表示为 wl, wl + 1, ..., wr。他们必须满足以下条件:
- 等式 |wi - wi + 1| = 1 对于所有 i 必须成立 (l ≤ i < r);
- 不等式 2·wi - wi + 1 - wi - 1 ≥ 0 对于所有 i (l < i < r) 必须成立。
删除 w 的所选子串后,您将获得 vr - l + 1 分。当存在正确的子字符串时,您可以一次又一次地执行所描述的操作。您也可以随时结束游戏。你的任务是计算你在游戏中可以获得的最高总分。
输入
第一行包含一个整数 n (1 ≤ n ≤ 400) — w 的初始长度。第二行包含 n 个整数 v1, v2, ..., vn (0 ≤ |vi| ≤ 2000) — 操作成本。下一行包含 n 个整数 w1, w2, ..., wn (1 ≤ wi ≤ 109) — 初始 w。
输出
打印一个整数 - 您可以获得的最大总分。
示例
输入 #1
3 0 0 3 1 2 1
输出 #1
3
输入 #2
6 1 4 5 6 7 1000 2 1 1 2 2 3
输出 #2
12