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}$

请输出一个整数，表示所需的最小金额。

## 限制条件 - $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 翻译