题目描述 (pdstring)

强哥有一个长度为 $n$ 且由小写字母构成的字符串 $S$。

强哥现在可以对 $S$ 做一些修改，但修改是需要代价的，将字母 $c_1$ 变成 $c_2(c_1\ne c_2)$ 的代价为 $v_{c_2}$，其中 $v$ 是一个长度为 $26$ 的数组。（为了方便理解，规定字母 a 对应数字 $1$，字母 b 对应数字 $2$，以此类推）

强哥在做上述修改前可以先选择两个位置并交换两个位置上的字母（该操作最多做一次且代价为 $0$），然后再将字母随意修改。

强哥想要知道将 $S$ 变成回文串的最小代价，保证 $n$ 能被 $2$ 整除。

输入格式(pdstring.in)

输入第一行包含一个整数 $n$，表示字符串的长度。

输入第二行包含 $26$ 个整数，表示代价数组 $v$。

输入第三行包含一个字符串 $S$。

输出格式(pdstring.out)

输出共一行，表示将 $S$ 变为回文串的最小代价。

6
5 3 2 4 7 6 2 5 1 4 6 2 5 1 4 6 2 5 1 4 6 2 5 1 4 7
abbaaa

0

样例 1 解释

在修改前将第 $3$ 个字母与第 $5$ 个字母进行交换，$S$ 变为 abaaba，已经是一个回文串，所以最小代价为 $0$。

6
5 3 2 4 7 6 2 5 1 4 6 2 5 1 4 6 2 5 1 4 6 2 5 1 4 7
bbbaaa

2

20
5 3 2 4 7 6 2 5 1 4 6 2 5 1 4 6 2 5 1 4 6 2 5 1 4 7
luotianyirainybunnyl

9

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 500$。
• 对于 $50\%$ 的数据，保证 $n \le 5000$。
• 对于另 $30\%$ 的数据，保证 $\forall 1\le i\le n$，$S_i\in \{a,b\}$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$0\le v_i\le 10^9$，$n$ 是偶数。