现在有一个字符串，你可以对这个字符串进行拆分，如 `abcvsdaas` 可以拆分为 `abc|vs|d|aas`，现在再给你一个字典，要求分割成的每一个子串必须要有包含其中的任意一个单词。那么最多可以分为几个子串呢？

第一行，一行字符串

第二行一个正整数 $N$，表示字典中字符串的数量

接下来 $N$ 行，每行一个字符串 $A_i$，表示字典中的一个字符串。

一个整数，表示最多的分割数。

特殊情况：

如果原字符串不能被分割，请输出 $0$。



数据范围：


对于 $100\%$ 的数据，$1\leq |A_i| \leq |s|\leq 300，1\leq N\leq 500$。

其中，$|s|,|A_i|$ 表示字符串 $s$ 与 $A_i$ 的长度。