题面描述

定义长度为 $n$ 的“好串”$s$ 满足：

$$\forall i\in[2,n],|s_i-s_{i-1}|=1\\\forall i\in[2,n-1],s_i\ge \frac{s_{i-1}+s_{i+1}}{2} $$

给你两个长度为 $n$ 的序列 $a,v$，每次选择一段“好”的、长度为 $i$ 的子串删掉，剩下的子串前后拼接，并获得 $v_i$ 的价值，不一定要删完。

求可能获得的最大价值。

输入格式

从 good.in 中读入数据。

第一行一个数 $n$。

接下来一行 $n$ 个数 $v_i$。

接下来一行 $n$ 个数 $a_i$。

输入格式

输出到 good.out 中。

仅一行一个整数，表示可能获得的最大价值。

样例

样例 1

3
0 0 3
1 2 1

3

样例 2

6
1 4 5 6 7 1000
2 1 1 2 2 3

12

样例 3

见附加文件中 good2.in 与 good2.out。

数据范围

• 对于 $10\%$ 的数据，$n\le 5$，$|v_i|\le 5$，$a_i\le 5$。
• 对于 $30\%$ 的数据，$n\le 20$。
• 对于另外 $20\%$ 的数据，$|v_i|\le 1$。
• 对于 $100\%$ 的数据，$1\le n\le 400$，$|v_i|\le 10^5$，$1\le a_i\le 10^9$。