题目描述

BX 正在进行一个字符串游戏，他手上有一个字符串 $L$，以及其他一些字符串的集合 $S$，然后他可以进行以下操作：对于一个在集合 $S$ 中的字符串 $p$，如果 $p$ 在 $L$ 中出现，BX 就可以选择是否将其删除，如果删除，则将删除后 $L$ 分裂成的左右两部分合并。举个例子，$L=\texttt{abcdefg}$ , $S={\texttt{de}}$，如果 BX 选择将 $\texttt{de}$ 从 $L$ 中删去，则删后的 $L=\texttt{abcfg}$。现在 BX 可以进行任意多次操作（删的次数，顺序都随意），他想知道最后 $L$ 串的最短长度是多少。

输入格式

输入的第一行包含一个字符串，表示 $L$。第二行包含一个数字 $n$，表示集合 $S$ 中元素个数。

以下 $n$ 行，每行一个字符串，表示 $S$ 中的一个元素。输入字符串都只包含小写字母。

输出格式

输出一个整数，表示 $L$ 的最短长度。

样例

input

aaabccd
3
ac
abc
aaa

output

2

aaabccd
aacd
ad

数据范围与提示

$|L|<151$, $|S|<31$, $S$ 中的每个元素 $|p|<21$。