奸商

Problem Description

你是一个奸商，你甚至将金钱看得比你的性命还重要，所以你被巨人抓了起来。 巨人给了你一个字符串，字符串中只包含字母表中的前 $17$ 个字母，即 $a \sim q$，并将会对所有长度 $\ge len$ 的子串进行检查，如果有任意一个子串不是优秀的，他就会处决你。 对于一个长度为 $n$ 的字符串 $s$，如果至少存在一个位置 $i \thickspace (1 \leq i \leq n)$ 满足 $s[i] = s[n + 1 - i]$，就称此字符串是优秀的。 现在，你可以花费一定代价使巨人对某些字母产生幻视，例如，如果巨人对字母 $d$ 产生幻视，那么在检查过程中，巨人可能会将字符 $'d'$ 识别成某个 $ascii$ 码 $\ge$ $'d'$ 且 $ascii$ 码 $\leq$ $'q'$ 的字符，即 $'d'$，$'e'$，$'f'$，$\dots$，$'q'$。请注意：

• 巨人会对字符串中所有的字符 $'d'$ 产生幻视；
• 巨人在检查不同子串时，可能会对同一个字符 $'d'$ 有不同的幻视。 例如，对于字符串 $acde$，假设巨人仅对字母 $a$ 产生幻视：
• 检查不优秀的子串 $acde$ 时，巨人可能识别成优秀的字符串 $ecde$；
• 检查不优秀的子串 $ac$ 时，巨人可能识别成优秀的字符串 $cc$。 前文提到，你爱财如命，所以你希望在有生还希望的前提下，花费最小的代价，请你打印这个代价。

Input

第一行包含一个整数 $T$，表示测试数据的组数，$1 \leq T \leq 100$。 对于每组测试数据： 第一行包含一个整数 $n$，表示字符串的长度； 第二行给出一个长度为 $n$ 的字符串； 第三行包含 $17$ 个整数 $w_i \thickspace (1 \leq w_i \leq 1e6)$，分别表示使巨人对字母 $a \sim q$ 产生幻视需要的代价； 第四行包含一个整数 $len \thickspace (len \leq n)$，巨人会对所有长度 $\ge len$ 的子串进行检查。 数据保证：$\sum n \leq 3000$。

Output

请你打印在有生还希望的前提下，花费的最小代价。

Sample Input

1
5
encle
1 1 8 3 4 4 8 4 2 4 6 8 9 8 2 2 8
2

Sample Output

12

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）