

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 425 点
問題文
あなたは最初、空文字列 S を持っています。
さらに、文字列がいくつか入った袋 1,2,\dots,N があります。
袋 i には A_i 個の文字列 S_{i,1},S_{i,2},\dots,S_{i,A_i} が入っています。
これから、以下の手順を i=1,2,\dots,N について繰り返します。
- 以下のふたつの行動のうち、どちらかを選択して行う。
- 1 円を支払い、袋 i からちょうどひとつの文字列を選択して S の末尾に連結する。
- 何もしない。
文字列 T が与えられるとき、最終的に S と T を一致させるために必要な最小の金額を求めてください。
但し、どのようにしても最終的な S を T に一致させることができない場合、 -1
と出力してください。
制約
- T は長さ 1 以上 100 以下の英小文字からなる文字列
- N は 1 以上 100 以下の整数
- A_i は 1 以上 10 以下の整数
- S_{i,j} は長さ 1 以上 10 以下の英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
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
abcde 3 3 ab abc abcd 4 f c cd bcde 2 e de
出力例 1
2
例えば、以下のようにすると 2 円で最終的な S と T を一致させることができ、これが必要な金額の最低値であることが示せます。
- i=1 について、袋 1 から
abc
を選択し S の末尾に連結する。 S=abc
となる。 - i=2 について、何もしない。
- i=3 について、袋 3 から
de
を選択し S の末尾に連結する。 S=abcde
となる。
入力例 2
abcde 3 2 ab abc 3 f c bcde 1 e
出力例 2
-1
どのようにしても最終的な S と T を一致させることができないので、 -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
Score: 425 points
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