小 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 变为回文串的最小代价。

样例 3 解释

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

数据规模与约定

• 对于 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 是偶数。