一个关于序列的游戏

时间限制:5s      空间限制:128MB

题目描述

有一个序列,你可以在上面删除符合要求的连续段若干次。每次删除都会得到连续段长度对应的分数。
需要符合的要求为:
1、相邻两个元素相差为1
2、如果某个元素不在连续段的最左或最右,那么这个元素就不能同时小于相邻的左右两个元素。
“1、2、3、4、3” “1、2” “3、2” “3”都符合条件。
显然,删除掉连续段后,这个段的左边和右边并在一起成为相邻元素。
 
你的任务是对于给出的序列,计算出可能获得的最大总分。
 


输入格式

第一行一个整数N,表示序列长度
第二行N个数,V1、V2.....VN,代表每个长度对应的分数。
第三行N个数,A1、A2.....AN,代表初始序列的每个元素。


输出格式

一个数,可以获得的最大总分


样例输入

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

样例输出

11

提示


【样例说明】
3 1 2 34 10 --->3 4 10    V3=6
3 4 10 ---> 10           V2=5
5+6=11
【数据范围】
对于10%的数据,N<=3
对于40%的数据,N<=10
对于70%的数据,N<=70
对于100%的数据,1<=N<=150, -10000<=Vi<=10000,0<=Ai<=1000 000 000.相同的Ai不会超过7个


题目来源

Dp