「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现)
G. 忘记密码
单点时限: 3.0 sec
内存限制: 256 MB
起初你想了 $N$ 个长度均为 $k$ 的、由英文小写字母组成的密码 $a_1, a_2, \ldots, a_N$，为了避免自己忘记，你把它们藏起来：你创造了 $s_1, s_2, \ldots, s_N$ 个 $N$ 个字符串，使得 $a_i$ 是 $s_i$ 的子串。
为了避免自己看到 $s_i$ 的时候也想不起自己设的密码，你把 $a_1, a_2, \ldots, a_N$ 按顺序藏在了字符串 $T$ 中。也就是说 $T$ 是 $c_1 a_1 c_2 a_2 \cdots c_N a_N c_{N+1}$，其中 $c_i$ $(1 \leq i \leq N+1)$ 可以是空串。
但是不幸的是，你最终还是忘记了自己设置的密码。现在有 $s_1, s_2, \ldots, s_N$ 和 $T$，你想知道密码长度最大有可能是多少，即 $k$ 的最大值。
输入格式
输入包含多个测试文件，每个测试文件包含单组测试数据。
第一行是字符串 $T$。
第二行是一个整数 $N$ $(1 \leq N \leq 10)$。
第 $3$ 至 $N+2$ 行，每行一个字符串，分别表示 $s_1, s_2, \ldots, s_N$。
字符串由小写字母组成。
数据约定：
- 对于 30% 的数据，满足：$len(T) \leq 100, \sum_i len(s_i) \leq 500$。
- 对于 60% 的数据，满足：$len(T) \leq 20~000, \sum_i len(s_i) \leq 20~000$。
- 对于 100% 的数据，满足：$1 \leq len(T) \leq 250~000, \sum_i len(s_i) \leq 250~000$。
输出格式
一行一个整数，输出 $k$ 的最大值。
如果无解，输出 $-1$。
样例
Input
abcxzwwwyzxxyzzz 3 yzabcabc ppwwwwwwwpp wxxypp
Output
3
Input
xxxxxxxxxx 3 a b c
Output
-1
Input
tttttt 1 ttttttt
Output
6
提示
样例 1：$a_1, a_2, a_3$ 依次为 abc, www, xxy。
通知
比赛状态发生变化，点 OK 刷新。
通知