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

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

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