撰写博客

题目描述

小明发了一篇博客，由 $n$ 个小写英文字母组成。

但是写完这篇博客之后，小明发现博客由于包含一些词语，被自动隐藏了。

具体地，这些词语有 $m$ 个，分别为 $T_{1}$ , $T_{2}$ , $\dots$ , $T_{m}$ 。

小明发现，只要包含了其中某个词语，博客就会被自动隐藏。换言之，对于任意 $1 \leq i \leq m$ ， $T_{i}$ 都不能是最终发表的博客 $S$ 的子串。

于是小明决定在原来的博客 $S$ 上把一部分字母替换成空格，使得它不再包含任何词语。

小明发现如果她把第 $i$ 个字母替换成空格，那么整篇博客的价值会减少 $a_{i}$ 。

小明想要知道，如何替换可以得到一篇不会被自动隐藏的博客，而价值的减少量最少。

值得一提的是，如果小明把一个字母替换成空格，那么与之相邻的两个字母也不会变得连续。

但是小明请你帮他求出价值的最少减少量。

第一行两个正整数 $n$ ， $m$ ，表示小明初始的博客长度以及词语个数。

第二行一个长度为 $n$ 的，仅由小写字母组成的字符串 $S$ ，表示小明初始的博客。

第三行 $n$ 个空格隔开的整数 $a_{1}$ , $a_{2}$ , $\dots$ , $a_{n}$ ，其中第 $i$ 个数 $a_{i}$ 表示把第 $i$ 个字母改成空格导致的整篇博客价值减少量。

接下来 $m$ 行，每行一个仅由小写字母组成的字符串 $T_{i}$ ，表示一个词语。

输出一行一个整数表示整篇博客价值减少量的最小值。

对于所有测试数据， $1 \leq n=|S| \leq 2 \times 10^{5}$ ， $1 < m < 10$ ， $1 \leq |T_{i}| \leq 2 \times 10^{5}$ ， $0 \leq a_{i} \leq 1000$ 。

5 3
abcde
3 1 3 1 3
abc
bcd
cde