[ABC344] D - String Bags

D - String Bags

Time Limit: 2 sec / Memory Limit: 1024 MB

题面

你初始拥有一个空字符串。
另外，有个袋子，每个袋子里装有一些字符串。
第个袋子里包含个字符串。

你需要重复以下步骤，：

• 选择并执行以下两种操作中的一种：
  • 付出1日元，从第个袋子中选择一个字符串，然后将其连接到的末尾。
  • 什么都不做。

给定一个字符串，找到使最终的等于所需的最小金额。
如果无法使最终的等于，则输出-1。

限制条件

• 是一个由小写英文字母组成且长度在到之间的字符串。
• 是一个介于到之间的整数。
• 是一个介于到之间的整数。
• 是一个由小写英文字母组成且长度在到之间的字符串。

---

输入

输入以标准格式给出，如下所示：

输出

以整数形式输出答案。

---

输入样例 1

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

输出样例 1

2

例如，以下操作使最终的等于并且需要两日元，可以证明这是所需的最小金额。

• 对于，从第个袋子中选择abc，并将其连接到的末尾，得到 abc。
• 对于，什么都不做。
• 对于，从第个袋子中选择de，并将其连接到的末尾，得到 abcde。

---

输入样例 2

abcde
3
2 ab abc
3 f c bcde
1 e

输出样例 2

-1

无法使最终的等于，因此输出-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