问题 C: 奸商

你是一个奸商，你甚至将金钱看得比你的性命还重要，所以你被巨人抓了起来。

巨人给了你一个字符串，字符串中只包含字母表中的前 $17$ 个字母，即 $a\sim q$，并将会对所有长度 $\ge len$ 的子串进行检查，如果有任意一个子串不是优秀的，他就会处决你。

对于一个长度为 $n$ 的字符串 $s$，如果至少存在一个位置 $i(1\le i\le n)$ 满足 $s[i]=s[n+1-i]$，就称此字符串是优秀的。

现在，你可以花费一定代价使巨人对某些字母产生幻视，例如，如果巨人对字母 $d$ 产生幻视，那么在检查过程中，巨人可能会将字符 ′d′′d′ 识别成某个 $ascii$ 码 $\ge$ ′d′′d′ 且 $ascii$ 码 $\le$ ′q′′q′ 的字符，即 ′d′′d′，′e′′e′，′f′′f′，$\dots$，′q′′q′。请注意：

• 巨人会对字符串中所有的字符 ′d′′d′ 产生幻视；
• 巨人在检查不同子串时，可能会对同一个字符 ′d′′d′ 有不同的幻视。

例如，对于字符串 $acde$，假设巨人仅对字母 $a$ 产生幻视：

• 检查不优秀的子串 $acde$ 时，巨人可能识别成优秀的字符串 $ecde$；
• 检查不优秀的子串 $ac$ 时，巨人可能识别成优秀的字符串 $cc$。

前文提到，你爱财如命，所以你希望在有生还希望的前提下，花费最小的代价，请你打印这个代价。

第一行包含一个整数 $T$，表示测试数据的组数，$1\le T\le 100$。

对于每组测试数据：

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

第二行给出一个长度为 $n$ 的字符串；

第三行包含 $17$ 个整数 wi(1≤wi≤1e6)wi(1≤wi≤1e6)，分别表示使巨人对字母 $a\sim q$ 产生幻视需要的代价；

第四行包含一个整数 $len(len\le n)$，巨人会对所有长度 $\ge len$ 的子串进行检查。

数据保证：$\sum n\le 3000$。