CF150D Mission Impassable

市场上的小摊终于迎来了万众期待的游戏《The Colder Scrools V: Nvodsk》。这款游戏难度极高，大多数学生都无法完成最后一个任务（“我们不去 Nvodsk……”）。这让冬季考试岌岌可危。校长甚至开始考虑是否要把冬考推迟到四月（实际上，他也想亲自通关）。但就在这时，一位陌生人出现在他办公室门口。“午安。我叫 Chuck，专门解决各种问题。”——他说。 然而他俩坐在一起依然无法通关。问题在于，要击败最终 Boss，必须完美掌控字母排列的艺术。这需要一位真正的魔法师。你能想象当两位魔法师展开竞技会发生什么吗…… 让我们用更正式的语言描述：给你一个字符串以及一组整数 $a_{i}$。你可以选择字符串中的任意回文子串并将其删除。这样你会获得 $a_{k}$ 分，其中 $k$ 表示被删除回文串的长度。对于某些 $k$，若 $a_{k}=-1$，则禁止删除长度为 $k$ 的回文子串。每次删除子串后，剩余部分会自动拼接在一起，字符串中不会出现空隙。只要能删除至少一个允许的回文子串，这一过程就可以一直重复。所有获得的分数会累计相加。 请你求出最多可以获得多少分数。 “哦，”Chuck 站起身说，“我以前也像你们一样喜欢删除回文，但是有一天我膝盖中了一箭。”

第一行输入一个整数 $l$（$1\leq l\leq 150$）——字符串的长度。 第二行输入 $l$ 个整数 $a_{k}$（$-1\leq a_{k}\leq 10^{5}$）——删除不同长度回文子串时获得的分数。 第三行输入恰好 $l$ 个小写拉丁字母——表示原始字符串。输入字符串中除了换行符外不含其它字符。

输出一个整数——在给定字符串上最多能获得多少分数。

在第一个样例中，无法删除任何子串，因此最佳得分为 $0$。 在第二个样例中，仅允许删除长度为 $1$ 的回文，因此删除整个字符串会获得 $7$ 分。 在第三个样例中，最优策略为：先删除字符 c，然后依次删除 aa、bb、最后再删掉 aa。这样获得 $1+3\times 5=16$ 分。 由 ChatGPT 5 翻译