分数: 425 点
问题陈述
您最初有一个空字符串 S.
另外还有袋子 1, 2, \dots, N,每个包含一些字符串。
包 i 包含 A_i 字符串 S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.
您将重复以下步骤 i = 1, 2, \dots, N:
- 选择并执行以下两个操作之一:
- 支付 1 日元,从包里选择一根绳子 i,并将其连接到末尾 S.
- 什么都不做。
给定一个字符串 T,求最终完成所需的最低金额 S 等于 T.
如果没办法进入决赛 S 等于 T,打印 -1.
约束
- T 是由小写英文字母组成的字符串,长度介于 1 和 100,包括在内。
- N 是介于 1 和 100,包括在内。
- A_i 是介于 1 和 10,包括在内。
- S_{i,j} 是由小写英文字母组成的字符串,长度介于 1 和 10,包括在内。
输入
输入由标准输入按以下格式给出:
T
N
A_1 S_{1,1} S_{1,2} \dots S_{1,A_1}
A_2 S_{2,1} S_{2,2} \dots S_{2,A_2}
\vdots
A_N S_{N,1} S_{N,2} \dots S_{N,A_N}
输出
将答案打印为整数。
示例输入 1
abcde 3 3 ab abc abcd 4 f c cd bcde 2 e de
示例输出 1
2
例如,执行以下操作会使最终结果 S 等于 T 两日元,可以显示为所需的最低金额。
- 对于 i=1,选择
abc从袋子里 1 并将其连接到末尾 S, 制作 S=abc. - 对于 i=2,什么也不做。
- 对于 i=3,选择
de从袋子里 3 并将其连接到末尾 S, 制作 S=abcde.
示例输入 2
abcde 3 2 ab abc 3 f c bcde 1 e
示例输出 2
-1
没办法进决赛 S 等于 T,所以打印 -1.
示例输入 3
aaabbbbcccc 6 2 aa aaa 2 dd ddd 2 ab aabb 4 bbaa bbbc bbb bbcc 2 cc bcc 3 ccc cccc ccccc
示例输出 3
4