T3 回文（palindrome）

题目描述

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

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

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

小 C 想要知道将 $S$ 变成回文串的最小代价，保证 $2|n$。

输入格式

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

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

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

输出格式

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

样例 1 输入

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

样例 1 输出

0

样例 1 解释

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

样例 2 输入

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 输出

2

样例 3 输入

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

样例 3 输出

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$ 是偶数。