该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 L 想给小 L 写信。

他洋洋洒洒地写下了一封信 $S$（为一个不含空格，字符集为小写字母的字符串）。但是在他写完后，他意识到他实际想写的内容是 $T$。

但不幸的是，小 L 唯一的笔在此时掉下了桌子，摔断了。无奈的小 L 只能去删去 $S$ 的一些字符。

小 L 希望自己的信不能太杂乱，所以他每次只能选择涂掉（即删去）某种字符在当前信第一次（即最左边）出现的位置或最后一次（即最右边）出现的位置。

除此之外，小 L 还给他写的信的每个字符的美观度进行了打分，$S$ 中的第 $i$ 个字符的美观度为 $w_i$。

小 L 希望小 L 可以收到字尽可能清秀的信，所以他想知道，在能得到 $T$ 串的前提下，被涂掉的字符的美观度和最小能是多少。

但是可怜的小 L 想了很久也不知道他该怎么办，请你帮帮他！

输入格式

在文件 letter.in 中读入。

本题采用多组测试。

第一行两个非负整数 $tid,T$，分别表示测试点编号，数据组数。

对于每组数据：

第一行两个正整数 $n,m$，分别表示 $S,T$ 的长度。

第二行一个长度为 $n$ 的字符串 $S$。

第三行一个长度为 $m$ 的字符串 $T$。

第四行 $n$ 个非负整数 $w_i$。

输出格式

在文件 letter.out 中输出。

共输出 $T$ 行，每行对应一组数据的答案：

若小 L 能从串 $S$ 得到串 $T$，输出被删去的字符的最小美观度和；否则输出 -1。

样例

样例输入 #1

0 3
7 3
ababccb
abc
7 2 2 4 3 2 1
5 4
babab
baab
2 1 3 2 4
10 5
bbbbababaa
bbbab
5 1 1 0 5 1 1 2 4 4

样例输出 #1

7
-1
16

样例 1 解释

第一组数据：

$\texttt{ababccb} \to \texttt{ababcc} \to \texttt{ababc} \to \texttt{aabc} \to \texttt{abc}$，每次删去字符的美观度为 $1,2,2,2$，答案为 $1+2+2+2=7$。

样例 2 ～ 样例 5 见下发文件：letter2.in / letter2.out ～ letter5.in / letter5.out。其中样例 2 满足测试点 $1 \sim 2$ 的约束条件，样例 3 满足测试点 $3 \sim 6$ 的约束条件，样例 4 满足测试点 $10 \sim 12$ 的约束条件，样例 5 满足测试点 $17 \sim 20$ 的约束条件。

大样例

数据范围

特殊性质 A：字符串仅包含 $\texttt{a}$。

特殊性质 B：字符串随机均匀生成。

特殊性质 C：$w_i=1$。

对于所有数据，$1 \le T \le 3$，$1 \le n,m \le 2 \times 10^5$，$0 \le w_i \le 10^9$。