问题描述

$\color{red} PS：本题的名字和题面没有一点关系！！！纯粹是为了和《你好！ACM！》凑个对/doge$

给你一个主字符串 $s$ （$s$ 中的第 $i$ 个字符记为 $s_i$ ） 和 $n$ 个字符串 $t_i$ 。

现在你有一种选择操作：每次选择一个区间 $[L, R]$ ，将这个区间所包含的字符子串记为 $s[L, R]$ ， 需要保证 $s_L, s_{L+1}, s_{L+2}, \cdots , s_{R-1}, s_R$ 没有被选择过并且这个子字符串 $s[L, R]$ 等于其中一个字符串 $t_i$， 即$\exists i ~~ t_i = s[L, R]$。

现在，你需要选择若干次（可能为零次），使得没被选择的字符尽可能地少，请求出没被选择的字符最少为多少。

所有字符均为小写字符。

输入格式

第一行输入一个字符串 $s$ 。

第二行输入一个正整数 $n$ 。

接下来 $n$ 行，每行输入一个字符串 $t_i$ 。

输出格式

请求出没被选择的字符最少为多少。

输入样例

abcddd
3
ab
bc
ddd

输出样例

1

说明

在 $ab$ 和 $bc$ 中，你只能选择一个。如果你同时选择 $ab$ 和 $bc$ ，主字符串 $s$ 中的第二个字符 $b$ 就会被选择两次，不符合题意。

所以，符合题意的选择为 $ab,ddd$ 或者 $bc, ddd$。

这样的选择会让没被选择的字符数量最少，为 $1$ 。

评测数据规模

对于所有评测数据，$1 \le |s| \le 10^5$ ，$1 \le |t_i| \le 1000$ ，$1 \le n \le 100$