F. 忘记密码 - 「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (专业组)

仪表盘所有提交榜单

单点时限: 3.0 sec

内存限制: 256 MB

起初你想了 $N$ 个长度均为 $k$ 的、由英文小写字母组成的密码 $a_{1}, a_{2}, \dots, a_{N}$ ，为了避免自己忘记，你把它们藏起来：你创造了 $s_{1}, s_{2}, \dots, s_{N}$ 个 $N$ 个字符串，使得 $a_{i}$ 是 $s_{i}$ 的子串。

为了避免自己看到 $s_{i}$ 的时候也想不起自己设的密码，你把 $a_{1}, a_{2}, \dots, a_{N}$ 按顺序藏在了字符串 $T$ 中。也就是说 $T$ 是 $c_{1} a_{1} c_{2} a_{2} \dots c_{N} a_{N} c_{N + 1}$ ，其中 $c_{i}$ $(1 \leq i \leq N + 1)$ 可以是空串。

但是不幸的是，你最终还是忘记了自己设置的密码。现在有 $s_{1}, s_{2}, \dots, s_{N}$ 和 $T$ ，你想知道密码长度最大有可能是多少，即 $k$ 的最大值。

输入格式

输入包含多个测试文件，每个测试文件包含单组测试数据。

第一行是字符串 $T$ 。

第二行是一个整数 $N$ $(1 \leq N \leq 10)$ 。

第 $3$ 至 $N + 2$ 行，每行一个字符串，分别表示 $s_{1}, s_{2}, \dots, s_{N}$ 。

字符串由小写字母组成。

数据约定：

对于 30% 的数据，满足： $l e n (T) \leq 100, \sum_{i} l e n (s_{i}) \leq 500$ 。
对于 60% 的数据，满足： $l e n (T) \leq 20 000, \sum_{i} l e n (s_{i}) \leq 20 000$ 。
对于 100% 的数据，满足： $1 \leq l e n (T) \leq 250 000, \sum_{i} l e n (s_{i}) \leq 250 000$ 。

输出格式

一行一个整数，输出 $k$ 的最大值。

如果无解，输出 $- 1$ 。

样例

Input

abcxzwwwyzxxyzzz
3
yzabcabc
ppwwwwwwwpp
wxxypp

Output

Input

xxxxxxxxxx
3
a
b
c

Output

-1

Input

tttttt
1
ttttttt

Output

提示

样例 1： $a_{1}, a_{2}, a_{3}$ 依次为 abc, www, xxy。

NaN

A. 语言辨别 B. 计软联谊 C. 数青蛙 D. 玉米和葡萄 E. 限量供应 F. 忘记密码 G. 蚂蚁 H. 章鱼哥没有女朋友 I. 萝莉理论计算机科学家 J. 神奇怪兽在哪里 K. 简单几何题 L. 足球锦标赛

比赛状态发生变化，点 OK 刷新。

OK

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

输入格式

输出格式

样例

提示

题目列表

服务

开源

关于我们