103443: [Atcoder]ABC344 D - String Bags

Problem Statement

You initially have an empty string $S$.
Additionally, there are bags $1, 2, \dots, N$, each containing some strings.
Bag $i$ contains $A_i$ strings $S_{i,1}, S_{i,2}, \dots, S_{i,A_i}$.

You will repeat the following steps for $i = 1, 2, \dots, N$:

• Choose and perform one of the following two actions:
  • Pay $1$ yen, select exactly one string from bag $i$, and concatenate it to the end of $S$.
  • Do nothing.

Given a string $T$, find the minimum amount of money required to make the final $S$ equal $T$.
If there is no way to make the final $S$ equal $T$, print -1.

Constraints

• $T$ is a string consisting of lowercase English letters with length between $1$ and $100$, inclusive.
• $N$ is an integer between $1$ and $100$, inclusive.
• $A_i$ is an integer between $1$ and $10$, inclusive.
• $S_{i,j}$ is a string consisting of lowercase English letters with length between $1$ and $10$, inclusive.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

2

For example, doing the following makes the final $S$ equal $T$ with two yen, which can be shown to be the minimum amount required.

• For $i=1$, select abc from bag $1$ and concatenate it to the end of $S$, making $S=$ abc.
• For $i=2$, do nothing.
• For $i=3$, select de from bag $3$ and concatenate it to the end of $S$, making $S=$ abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final $S$ equal $T$, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4