问题描述

Indeed 公司的员工 A 先生正在提升他的字符串处理技能。A 先生目前正在解决的问题如下所示。

他想要通过连接一些回文来构造一个字符串。如果使用长度为 $i$ 的回文，将会产生 $C_i$ 的成本。此时，求构造字符串 $S$ 需要的最小成本和。注意，回文是指正向读和反向读都相同的字符串。此外，即使多次使用相同的回文，也要注意到每次使用的成本。

然而，A 先生无法解决这个问题。请帮助 A 先生编写一个程序来解决这个问题。

输入

输入从标准输入中以以下格式给出：

$N$

$S$

$C_1$ $C_2$ ... $C_N$

• 第 1 行为一个整数 $N (1 ≤ N ≤ 5000)$，表示字符串 $S$ 的长度。
• 第 2 行为字符串 $S$。
• 第 3 行为 $N$ 个整数，以空格分隔。其中第 $i (1 ≤ i ≤ N)$ 个整数 $C_i (1 ≤ C_i ≤ 10^5)$ 表示使用长度为 $i$ 的回文的成本。

子任务

本问题设有部分测试点。

• 如果对于数据集 1 满足 $N ≤ 200$，则答案正确可得 40 分。
• 如果对于所有测试用例都正确，将额外获得 60 分。

输出

输出构造字符串 $S$ 时所需的最小成本和，以一行输出。末尾包含换行符。

示例输入1

9
indeednow
1 1 1 1 1 1 1 1 1

示例输出1

4

在此示例中，将 i + ndeedn + o + w 进行连接的总成本为 4。

示例输入2

9
indeednow
10 4 1 99 99 99 99 99 99

示例输出2

74

在此示例中，将 i + ndeedn + o + w 进行连接的总成本为 129，

将 i + n + d + ee + d + n + o + w 进行连接的总成本为 74。

示例输入3

12
abcbaabcbcbc
20 13 15 29 38 43 76 58 23 128 99999 100000

示例输出3

78