题面翻译

给定仅有英文小写字母的字符串 $S$，可以对其进行若干次操作，每次将 $S$ 中某个字符替换为 *。给定 $n$ 个仅有英文小写字母的模式串，要求进行操作使得 $S$ 中不存在任意子串与模式串相同。最小化操作次数，输出最小值。

样例 #1

样例输入 #1

abcdefghijklmn
3
abcd
ijk
ghi

样例输出 #1

2

样例 #2

样例输入 #2

atcoderbeginnercontest
1
abc

样例输出 #2

0

样例 #3

样例输入 #3

aaaaaaaaa
2
aa
xyz

样例输出 #3

4

提示

制約

• $1\ \leq\ |S|\ \leq\ 5\ \times\ 10^5$
• $1\ \leq\ N$
• $1\ \leq\ |T_i|$
• $\sum{|T_i|}\ \leq\ 5\ \times\ 10^5$