「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (大一组)

E. 忘记密码

单点时限: 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