G. 回文串魔法
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$ ,只包含小写字母。

再给定一个长度为 $$$26$$$ 的数组 $$$v$$$，表示修改操作的代价。

你需要对字符串执行如下流程（按顺序）：

1.选择两个位置 $$$i,j$$$（允许 $$$i=j$$$），交换 $$$s_i$$$ 与 $$$s_j$$$，代价为 $$$0$$$。（必须做该操作恰好一次）

2.然后你可以对任意位置进行若干次字符修改（也可以不修改）。每次把某位置改为字母 $$$c$$$ 的代价为 $$$v_c$$$。

你的目标是使最终字符串变为回文串，并使总代价最小。

一个长度为 $$$n$$$ 的字符串 $$$t$$$ 称为回文串，当且仅当对所有 $$$1\le i\le n$$$ 都满足 $$$t_i = t_{n - i + 1}$$$

Input

第一行一个整数 $$$n$$$（$$$1 \le n \le 10^6$$$）。

第二行一个长度为 $$$n$$$ 的仅含小写字母的字符串 $$$s$$$。

第三行 $$$26$$$ 个整数 $$$v_a,v_b,\dots,v_z$$$，其中 $$$v_c$$$ （$$$0 \le v_c \le 10^9$$$）表示把某个字符改为字母 $$$c$$$ 的代价。

Output

输出一行一个整数，表示把 $$$s$$$ 变成回文串的最小总代价。

Examples
Input
10
btpyjjyptf
14 18 13 13 12 7 6 4 16 16 6 4 19 11 3 15 14 10 6 10 2 6 14 8 11 7
Output
4
Input
6
tarjen
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
Output
163