Ugrás

Péter és Márió játszanak. Márió azt állítja, hogy az alábbi pályán össze tud szedni 30 aranyat…

|                             7                 9    |
|                    3        *              9  *    |
|                    *     5  *  8           *  *    |
|              1     *  9  *  *  *  5        *  *    |
|              *  6  *  *  *  *  *  *  6  5  *  *    |
|           0  *  *  *  *  *  *  *  *  *  *  *  *  0 |
|           *  *  *  *  *  *  *  *  *  *  *  *  *  * |
|----------------------------------------------------|
|magasság:  1  3  2  5  3  4  6  4  3  2  2  5  6  1 |
|   érint:  1  2     4        7  8  9 10          14 |
|   arany:  0  1     3        7  8  5  6           0 |

Miről van szó? A fenti ábrán *-okból álló tornyokat látunk, alattuk az $M_i$ magasságukkal. A játékos kezdetben a balszélső 1 magas tornyon áll, a cél eljutni a jobbszélső 1 magas toronyhoz. Bármilyen toronyból bármely más tőle jobbra levő toronyra el tud ugrani, de ennél a pályánál van még egy fontos szabály: az érintett tornyok magasságainak először szigorúan növekedni kell, majd szigorúan csökkenni. Ha egy ugrássorozat érinti az $i$ .-ik tornyot akkor a játékos összeszedi a torony tetején levő $V_i$ aranyat. Az ábrán a vonal alatti második sorban a Márió által érintett tornyok sorszámai vannak, látható hogy az ugrássorozat megfelel a pálya szabályainak és a játékos jutalma valóban 30 aranytallér. Találhatunk még más legális ugrássorozatokat, például tekintsük a következő sorszámokat:

1-3-5-6-12-13-14     ennek jutalma 38
1-3-5-6-7-8-9-10-14  melynél a jutalom 46 (ez a legjobb)

Péter szeretné előre kiszámolni, hogy egy adott pálya esetén mennyi a maximálisan szerezhető arany (

X

). Segítsünk neki!

Bemenet specifikáció

Az első sorban szerepel a tornyok $N$ száma. A második sorban az $N$ szóközzel elválasztott szám: a tornyok $M_i$ magasságai. A harmadikban $N$ szóközzel elválasztott szám a megfelelő $V_i$ jutalmakat jelenti. A balszélső és jobbszélső torony mindig egy-egy 1 magasságú és 0 arany van rajta - a többi torony mindig 1-nél magasabb.