AT_abc344_d [ABC344D] String Bags

题目描述

你一开始拥有一个空字符串 $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}$ $\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

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

abcde
3
2 ab abc
3 f c bcde
1 e

输出 #2

-1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $T$ 是一个长度在 $1$ 到 $100$ 之间的仅包含小写英文字母的字符串。
• $N$ 是 $1$ 到 $100$ 之间的整数。
• $A_i$ 是 $1$ 到 $10$ 之间的整数。
• $S_{i,j}$ 是长度在 $1$ 到 $10$ 之间的仅包含小写英文字母的字符串。

样例解释 1

例如，可以按如下方式用 $2$ 元使最终的 $S$ 与 $T$ 相同，并且这就是所需金额的最小值。

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

样例解释 2

无论如何都无法使最终的 $S$ 与 $T$ 相同，因此请输出 $-1$。

由 ChatGPT 4.1 翻译