← 返回题目列表

AtCoder · abc344_d

G. 绳袋

中文机器翻译题面 查看原题

分数: 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