Jump

Peter and Mario are playing a game. Mario says he can get 30 golds on this level…

|                             7                 9    |
|                    3        *              9  *    |
|                    *     5  *  8           *  *    |
|              1     *  9  *  *  *  5        *  *    |
|              *  6  *  *  *  *  *  *  6  5  *  *    |
|           0  *  *  *  *  *  *  *  *  *  *  *  *  0 |
|           *  *  *  *  *  *  *  *  *  *  *  *  *  * |
|----------------------------------------------------|
|  height:  1  3  2  5  3  4  6  4  3  2  2  5  6  1 |
|    jump:  1  2     4        7  8  9 10          14 |
|    gold:  0  1     3        7  8  5  6           0 |

What is this game about? On the figure below we can see towers made from *-s. Under them we can see their heights ( $M_i$ ). The player starts at the leftmost tower and goal is to get to the rightmost tower. It’s possible to jump from any tower to any other tower on its right. But there’s a catch: first the heights of the towers the player jumps on should strictly increase in height then strictly decrease. If a player jumps on a $i$ -th tower he collects the gold ( $V_i$ ) on top of the tower. In the above figure’s jump row, you can see the indices of the towers the player jumped on. It can be seen that this is a valid sequence of jumps and the amount of gold he collects is 30. We can find other valid sequences of jumps, for example:

1-3-5-6-12-13-14     the amount of collected gold: 38
1-3-5-6-7-8-9-10-14  46 gold collected (it is the best one)

Peter would like to calculate for a given level: what is the maximal amount of gold that can be collected with a valid jumping sequence (X). Help him!

Input specification

On the first line of the input, there’s $N$ the number of towers. On the second line of the input there are $N$ integers: the heights of the towers ( $M_i$ ). On the third line of the input there are $N$ integers: the amount of gold on top of each tower ( $V_i$ ). The first and last towers always have a height of $1$ and they have $0$ gold on top of them - the other towers always have larger than 1 height.