Description

给定一个整数序列，现在你可以对这个序列进行若干次删除操作，每次可以删掉序列中一段连续子序列，每次删除都会得到一定分数。

每次删除的连续子序列需要符合的条件为：

1. 序列中相邻两个元素差为 $1$

2. 若某元素不为连续子序列的首元素或尾元素，则它不能同时小于相邻的两个元素

例子： $(1, 2, 3, 4, 3), (1, 2), (3, 2), (3)$ 都符合条件; $(3, 2,1, 2, 3)$不符合条件。

一次删除操作执行后，所删除的连续子序列的两端将会并在一起成为相邻元素。

若一次操作删除的连续子序列长度为$m$,则你将会得到 $v_m$ 的分数。

现在对于给定序列，请你求出所能得到的最大总分。

Input Format

第一行一个整数 $n$ ，表示序列长度。

第二行 $n$ 个整数 $v_i$ ，表示删除序列长度所对应的分数。

第三行 $n$ 个整数而，表示初始时的序列。

Output Format

仅一行一个整数表示答案。

Sample

样例输入

6  
-100 5 6 10 0 0  
3 1 2 3 4 10  

样例输出

11

样例解释

3 x 1 2 3 x 4 10 -----> 3 4 10  
x 3 4 x 10 -----> 10  
5 + 6 = 11

Hint

10%的数据： $n \leq 3$

40%的数据： $n \leq 10$

70%的数据： $n \leq 70$

100%的数据：$1 \leq n \leq 150$ , $|v_i| \leq 10^4$ , $0 \leq a_i \leq 10^9$ , 相同的不超过 $7$ 个