该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

育华文创

题目描述

育华文创社团要拼接出目标文案 $T$。 一开始手里的文本 $S$ 为空。

一共有编号 $1,2,\dots,N$ 的 $N$ 个素材袋。 第 $i$ 个素材袋里面装有 $A_i$ 段文本素材：$S_{i,1},S_{i,2},\dots,S_{i,A_i}$。

你需要按顺序处理 $1$ 到 $N$ 每一个素材袋，对每个袋子二选一执行操作：

• 花费 $1$ 社团积分：从该袋子中挑选恰好一段素材，接在当前文本 $S$ 的末尾。
• 不花费积分：什么都不做。

要求处理完所有袋子之后，拼接得到的文本 $S$ 完全等于目标文案 $T$。 求需要消耗的最少社团积分；如果无论如何都无法拼出 $T$，输出 -1。

输入格式

第一行给出目标串 $T$ 和整数 $N$。 之后依次给出每一个素材袋的信息： 对于第 $i$ 个袋子，先给整数 $A_i$，随后跟随 $A_i$ 个字符串，代表袋内的素材。

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}

输出格式

输出达成目标需要的最少积分，无法完成输出 -1。

样例输入 #1

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

样例输出 #1

2

样例输入 #2

abcde 3
2 ab abc
3 f c bcde
1 e

样例输出 #2

-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

样例解释

样例1：

• 处理第1个素材袋，选取素材abc，花费1积分，此时 $S=\texttt{abc}$。
• 处理第2个素材袋，什么都不做。
• 处理第3个素材袋，选取素材de，花费1积分，此时 $S=\texttt{abcde}$。 总花费2积分，可以完成任务。

样例2：无论怎么选取素材，都无法拼出目标字符串abcde，输出 -1。

数据范围

• $1\le |T| \le 100$
• $1\le N \le 100$
• $1\le A_i \le 10$
• 每段素材字符串长度 $1\sim10$，全部由小写英文字母构成。