The sensational artist, Jasleen Royal is coming to perform in the cultural fest of NSIT, Moksha ! After her hit numbers in the recent Bollywood movies, the campus of NSIT is abuzz with people wanting to stand as close to the stage as possible. Now, the organiser of the event, Divanshu Brainy, is a smart guy. He knows that his colleagues will try to use his influence to get as close to the stage as possible. So, he has figured out a way to tackle this problem with an interesting game!
In the game, you have to modify a sequence of integers, called the g-string, and get points. However, you can only perform a single type of modification: deleting substrings. In other words, you can choose several contiguous elements of g and delete them from the sequence. Let's denote the sequence of chosen elements as g[l], g[l + 1], ..., g[r]. They must satisfy the conditions:
- For all i (l ≤ i < r), |g[i] - g[i + 1]| = 1 must hold true.
- The inequality (g[i] - g[i - 1]) ≥ (g[i + 1] - g[i]) must be true for all i (l < i < r).
After deleting the chosen substring of g, you gain val[r - l + 1] points. You can perform the described operation more than once while proper substrings exist. Also, you can end the game at any time. Since you want to secure a spot that is closer to the stage, you want to calculate the maximum total score you can get in the game!
Input format
The first line contains a single integer n (1 ≤ n ≤ 400) — the initial length of g-string. The second line contains n integers val[1], val[2], ..., valn — the costs of operations. The next line contains n integers g[1], g[2], ..., gn — the initial g-string.
Output format
Print a single integer — the maximum total score you can get.
