题目描述

给定一个字符串 $S$。高桥可以进行以下操作 $0$ 次或多次：

• 选择一个整数 $i$，使得 $1 \leq i \leq |S|$，并将 $S$ 的第 $i$ 个字符改为 *。

高桥的目标是使得 $S$ 不包含 $N$ 个字符串 $T_1,T_2,\ldots,T_N$ 中的任何一个作为子串。
找到实现这一目标所需的最小操作次数。

约束条件

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq N$
• $N$ 是一个整数。
• $1 \leq |T_i|$
• $\sum{|T_i|} \leq 5 \times 10^5$
• 若 $i \neq j$，则 $T_i \neq T_j$。
• $S$ 和 $T_i$ 是由小写英文字母组成的字符串。

输入

输入以以下格式从标准输入给出：

$S$ $N$ $T_1$ $T_2$ $\vdots$ $T_N$

输出

输出答案。

示例输入 1

abcdefghijklmn
3
abcd
ijk
ghi

示例输出 1

2

如果他分别选择 $1$ 和 $9$ 作为 $i$ 进行两次操作，$S$ 变为 *bcdefgh*jklmn；现在它不包含 abcd、ijk 或 ghi 作为子串。

示例输入 2

atcoderbeginnercontest
1
abc

示例输出 2

0

不需要任何操作。

示例输入 3

aaaaaaaaa
2
aa
xyz

示例输出 3

4