D - String Bags Editorial /

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