题目描述

强哥正在参加一个“爱心拼图”公益活动。
他一开始有一个空的爱心图案 $S$。
活动提供了编号为 $1,2,\dots,N$ 的若干个爱心材料包，每个材料包中装有若干爱心碎片。
材料包 $i$ 中有 $A_i$ 个爱心碎片，分别为 $S_{i,1},S_{i,2},\dots,S_{i,A_i}$。

接下来，强哥需要按顺序对每个材料包进行如下操作：

• 从以下两种行为中任选其一：
  • 花费 $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$ 相同，并且这就是所需爱心值的最小值。

• 对于材料包 $1$，选择爱心碎片 abc，拼接到 $S$ 的末尾。此时 $S=$ abc。
• 对于材料包 $2$，什么都不做。
• 对于材料包 $3$，选择爱心碎片 de，拼接到 $S$ 的末尾。此时 $S=$ abcde。

样例解释 2

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