字符串背包

题目描述

初始时有一个空字符串 $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
N
A_1 S_{1,1} S_{1,2} … S_{1,A_1}
A_2 S_{2,1} S_{2,2} … S_{2,A_2}
⋮
A_N S_{N,1} S_{N,2} … S_{N,A_N}

输出格式

输出答案（整数）。

样例

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

2

例如，按下述方式操作可以用 2 日元使最终的 $S$ 等于 $T$，可以证明这是所需的最小金额。

• 对 $i=1$，从袋子 1 中选择 abc 连接到 $S$ 末尾，得到 $S=$ abc。
• 对 $i=2$，什么都不做。
• 对 $i=3$，从袋子 3 中选择 de 连接到 $S$ 末尾，得到 $S=$ abcde。

abcde
3
2 ab abc
3 f c bcde
1 e

-1

无法使最终的 $S$ 等于 $T$，因此输出 -1。

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

4

数据范围

• $T$ 是由小写英文字母组成的字符串，长度为 $1$ 到 $100$。
• $N$ 是 $1$ 到 $100$ 的整数。
• $A_i$ 是 $1$ 到 $10$ 的整数。
• $S_{i,j}$ 是由小写英文字母组成的字符串，长度为 $1$ 到 $10$。