市场摊位现在有期待已久的游戏《The Colder Scrools V: Nvodsk》。结果游戏非常困难,大多数学生都无法完成最后一个任务(“我们不去恩沃茨克......”)。这威胁到了冬季考试。校长已经开始考虑是否应该将冬季考试推迟到四月(事实上,他想自己完成这个任务)。但突然,一个陌生人出现在他的办公室门口。 “下午好。我的名字是查克,我解决任何问题”——他说。
他们并肩而坐,但仍然无法完成任务。问题是,要杀死最终的老板,必须证明自己在管理信件方面拥有完美的技巧。一个人应该是一名真正的魔术师才能做到这一点。你能想象当魔术师开始比赛时会发生什么......
但让我们更正式地说:给你一个字符串和一组整数 ai。您可以选择任何回文子串并将其删除。此时我们收到一些等于 ak 的点,其中 k 是删除的回文的长度。对于某些k,ak = -1,这意味着禁止删除这样长度的回文串。删除子字符串后,剩余部分“一起移动”,即字符串在任何时刻都不会出现间隙。当字符串至少有一个可以删除的回文子串时,重复该过程。所有获得的积分都会被汇总。
确定可以获得的最大积分数。
“哦”——查克从椅子上站起来说——“我曾经喜欢删除回文,就像你一样,但有一天我的膝盖中了一箭”。
输入
第一行包含一个整数 l (1 ≤ l ≤ 150) — 字符串的长度。
第二行正好包含 l 个整数 ak (- 1 ≤ ak ≤ 105) — 玩家通过删除获得的分数。
第三行正好包含 l 个小写拉丁字母——玩家可以从中删除回文的原始字符串。除了字符串末尾的换行符之外,该行不包含其他字符。
输出
打印一个数字——如果弹奏给定的弦,可以获得的最大分数。
示例
输入 #1
7 -1 -1 -1 -1 -1 -1 -1 abacaba
输出 #1
0
输入 #2
7 1 -1 -1 -1 -1 -1 -1 abacaba
输出 #2
7
输入 #3
7 1 5 -1 -1 -1 -1 10 abacaba
输出 #3
16
注意
在第一个样本中,我们不能删除任何子字符串,因此最好的结果是 0。在第二个样本中,我们只能删除那些长度等于 1 的回文,因此,如果我们删除整个字符串,我们将得到 7 分。在第三个示例中,最佳策略是:首先删除字符 c,然后删除字符串 aa,然后删除 bb,最后删除一个 aa。这样我们就得到 1 + 3 * 5 = 16 分。