4.写博客

题目描述

小泽发了一篇博客，由$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$。

• 子任务$1$（$20$分）:$|S|$，$|T_{i}| \leq 100$ ;
• 子任务$2$（$30$分）:$|S|$，$|T_{i}| \leq 2000$;
• 子任务$3$（$20$分）:$|S|$，$|T_{i}| \leq 5000$ ;
• 子任务$4$（$30$分）:无特殊限制

样例

5 3
abcde
3 1 3 1 3
abc
bcd
cde

2