На прилавках магазинов появилась долгожданная игра The Colder Scrools V: XXXvodsk. Игра оказалась дьявольски сложна, и большинство студентов не могут пройти последнюю миссию («Мы не ходим в XXXводск...»), в связи с чем зимняя сессия оказалась под угрозой. Ректор уже подумывал о переносе сессии на апрель (ему и самому хотелось пройти эту миссию), когда на пороге его кабинета возник незнакомец. «Здравствуйте. Меня зовут Петрович, и я решаю любые проблемы», — сказал он.

Теперь они уже сидят вместе и все равно не могут пройти эту миссию. Ведь чтобы одолеть финального босса, требуется показать все свое мастерство в искусстве управления буквами. Нужно быть настоящими волшебниками, а уж что говорить, когда волшебники начинают соревноваться...

Но, давайте более формально: дана строка и набор целых чисел a_i. Разрешается выбрать любую подстроку, являющуюся палиндромом, и удалить ее. При этом мы получаем количество очков равное a_k, где k — длина удаляемого палиндрома. Для некоторых k a_k = -1, что означает, что удалять подстроки-палиндромы такой длины запрещено. После удаления подстроки оставшаяся часть «сдвигается», то есть строка ни в какой момент времени не содержит пропусков. Этот процесс повторяется, пока строка содержит хотя бы одну подстроку-палиндром, которую можно удалить. Все полученные очки суммируются.

Определите, какое максимальное количество очков можно получить.

«Эх», — сказал, вставая из-за стола, Петрович, — «когда-то я тоже любил удалять палиндромы, как и вы, но потом мне прострелили колено».