AT_indeednow_2015_finalb_c Palindrome Concatenation

Indeed 公司的一位员工 A 君正在提高他的字符串处理技巧。当前他面临的问题如下： 他希望通过拼接若干个回文串来构造一个给定的字符串 $S$。使用长度为 $i$ 的回文串会花费 $C_i$ 的成本。你的任务是找出构造字符串 $S$ 所需的最低总成本。回文串是指那些从左向右和从右向左读都相同的字符串。此外，如果同一个回文串被多次使用，每次都需要支付相应的成本。 然而，A 君对这一问题束手无策。请帮他写一个程序来解决这个问题。

输入通过标准输入给出，格式如下： > $N$ $S$ $C_1$ $C_2$ ... $C_N$ - 第一行是一个整数 $N\ (1 \leq N \leq 5000)$，表示字符串 $S$ 的长度。 - 第二行是由小写字母组成的字符串 $S$，长度为 $N$。 - 第三行有 $N$ 个空格分隔的整数，其中第 $i$ 个整数 $C_i\ (1 \leq C_i \leq 10^5)$ 表示使用长度为 $i$ 的回文串的成本。

输出构造字符串 $S$ 所需的最小总成本，结果为一行，末尾加一个换行符。

该问题设置了部分分： - 若在满足 $N \leq 200$ 的数据集上获得正确答案，可以得到 $40$ 分。 - 若在所有测试用例上都获得正确答案，额外可以得到 $60$ 分。 ### 样例解释 1 在这个例子中，通过拼接 `i` + `ndeedn` + `o` + `w`，总成本为 $4$。 ### 样例解释 2 在这个例子中，拼接 `i` + `ndeedn` + `o` + `w` 的成本为 $129$，但若改为 `i` + `n` + `d` + `ee` + `d` + `n` + `o` + `w`，总成本仅为 $74$。 **本翻译由 AI 自动生成**