E. Удаляем подстроки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

SmallR нравится игра под названием «Удаляем подстроки». В этой игре вам дана последовательность целых чисел w, можно изменять последовательность и зарабатывать очки. Единственный тип изменения, доступный в игре (неожиданно, правда?) — удаление подстрок. Более формально, можно выбрать несколько последовательных элементов w и удалить их из последовательности. Обозначим последовательность выбранных элементов как wl, wl + 1, ..., wr. Она должна удовлетворять следующим условиям:

  • равенство |wi - wi + 1| = 1 должно выполняться для всех i (l ≤ i < r);
  • неравенство wi - wi + 1 - wi - 1 ≥ 0 должно выполняться для всех i (l < i < r).

После удаления выбранной подстроки w, вы зарабатываете vr - l + 1 очков. Описанную операцию удаления можно выполнять снова и снова, пока существуют надлежащие подстроки. Также, можно в любой момент завершить игру. Ваша задача — по заданной последовательности w вычислить, какое максимальное количество очков можно получить в игре.

Входные данные

В первой строке содержится единственное целое число n (1 ≤ n ≤ 400) — изначальная длина w. Вторая строка содержит n целых чисел v1, v2, ..., vn (0 ≤ |vi| ≤ 2000) — цены операций. В следующей строке записано n целых чисел w1, w2, ..., wn (1 ≤ wi ≤ 109) — изначальная w.

Выходные данные

Выведите единственное целое число — наибольший общий счет, достижимый в игре.

Примеры
Входные данные
3
0 0 3
1 2 1
Выходные данные
3
Входные данные
6
1 4 5 6 7 1000
2 1 1 2 2 3
Выходные данные
12