String Bags

AtCoder

IDabc344_d

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

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

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`.

Input #2

abcde
3
2 ab abc
3 f c bcde
1 e

Output #2

\-1

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

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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "String Bags",
    "description": {
      "content": "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 r",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc344_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You initially have an empty string $S$.  \nAdditionally, there are bags $1, 2, \\dots, N$, each containing some strings.  \nBag $i$ contains $A_i$ strings $S_{i,1}, S_{i,2}, \\dots, S_{i,A_i}$.\nYou will r...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments