CF150D.Mission Impassable

Market stalls now have the long-awaited game The Colder Scrools V: Nvodsk. The game turned out to be difficult as hell and most students can't complete the last quest ("We don't go to Nvodsk..."). That threatened winter exams. The rector already started to wonder whether he should postpone the winter exams till April (in fact, he wanted to complete the quest himself). But all of a sudden a stranger appeared at the door of his office. "Good afternoon. My name is Chuck and I solve any problems" — he said.

And here they are sitting side by side but still they can't complete the mission. The thing is, to kill the final boss one should prove one's perfect skills in the art of managing letters. One should be a real magician to do that. And can you imagine what happens when magicians start competing...

But let's put it more formally: you are given a string and a set of integers a__i. You are allowed to choose any substring that is a palindrome and delete it. At that we receive some number of points equal to a__k, where k is the length of the deleted palindrome. For some k, a__k = -1, which means that deleting palindrome strings of such length is forbidden. After a substring is deleted, the remaining part "shifts together", that is, at no moment of time the string has gaps. The process is repeated while the string has at least one palindrome substring that can be deleted. All gained points are summed up.

Determine what maximum number of points can be earned.

"Oh" — said Chuck, raising from the chair, — "I used to love deleting palindromes, just like you, but one day I took an arrow in the Knee".

集市摊位上终于迎来了万众期待的游戏《寒霜编年史5：诺夫茨克》。这款游戏难度极高，大多数学生都无法完成最终任务（“我们不去诺夫茨克……”），这甚至威胁到了冬季考试的正常进行。校长已经开始考虑是否应将冬季考试推迟至四月（事实上，他本人正想亲自通关该任务）。就在此时，一位陌生人突然出现在他办公室门口。“下午好，我叫查克，任何问题我都能解决。”——他说道。

此刻，他们并肩而坐，却依然无法完成这一任务。原来，要击败最终Boss，玩家必须展现出对字母操控艺术的完美掌握，必须是一位真正的魔法大师才能做到这一点。而你能想象当魔法师们彼此竞争时会发生什么吗……

但让我们更形式化地描述这个问题：给定一个字符串以及一组整数 $a_i$。你可以任选一个回文子串并将其删除；删除长度为 $k$ 的回文子串可获得 $a_k$ 分。对于某些 $k$，有 $a_k = -1$，表示禁止删除长度为 $k$ 的回文子串。子串被删除后，剩余部分会“向中间靠拢”，即字符串在任意时刻均不会出现空隙。该过程可重复进行，只要字符串中仍存在一个可被删除的回文子串（即其长度 $k$ 满足 $a_k \neq -1$）。所有获得的分数累加起来。

请确定能够获得的最高总分。

“哦——”查克从椅子上站起来，说道，“我以前也特别喜欢删回文串，就像你一样，但有一天，我的膝盖中了一箭。”

The first line contains an integer l (1 ≤ l ≤ 150) — the length of the string.

The second line contains exactly l integers a__k ( - 1 ≤ a__k ≤ 105) — the points a player gains for deleting.

The third line contains exactly l lowercase Latin letters — the original string from which a player can delete palindromes. The line contains no other characters apart from the newline character at the end of the string.

第一行包含一个整数 $l$（$1 \leq l \leq 150$）—— 字符串的长度。

第二行包含恰好 $l$ 个整数 $a_k$（$-1 \leq a_k \leq 10^5$）—— 玩家删除字符时获得的分数。

第三行包含恰好 $l$ 个小写拉丁字母 —— 玩家可从中删除回文子串的原始字符串。该行除字符串末尾的换行符外，不包含其他任何字符。

Print a single number — the maximum number of points one can gain if he plays on the given string.

输出一个整数——即在给定字符串上进行游戏所能获得的最大分数。

In the first sample we cannot delete any substring, so the best result is 0. In the second sample we are allowed to delete only those palindromes whose length equals 1, thus, if we delete the whole string, we get 7 points. In the third sample the optimal strategy is: first we delete character c, then string aa, then bb, and the last one aa. At that we get 1 + 3 * 5 = 16 points.

在第一个样例中，我们无法删除任何子串，因此最优结果为 0。在第二个样例中，我们仅允许删除长度为 1 的回文子串，因此若删除整个字符串，则可获得 7 分。在第三个样例中，最优策略为：首先删除字符 c，然后删除字符串 aa，接着删除 bb，最后再删除 aa。此时我们共获得 1 + 3 \* 5 = 16 分。