9509: ABC344 —— D - String Bags
[Creator : ]
Description
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`.
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`.
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}$
```
```
$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.
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.
- $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.
Sample 1 Input
abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de
Sample 1 Output
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 2 Input
abcde
3
2 ab abc
3 f c bcde
1 e
Sample 2 Output
-1
There is no way to make the final S equal T, so print -1.
Sample 3 Input
aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc
Sample 3 Output
4