{"raw_statement":[{"iden":"problem statement","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 repeat the following steps for $i = 1, 2, \\dots, N$:\n\n*   Choose and perform one of the following two actions:\n    *   Pay $1$ yen, select exactly one string from bag $i$, and concatenate it to the end of $S$.\n    *   Do nothing.\n\nGiven a string $T$, find the minimum amount of money required to make the final $S$ equal $T$.  \nIf there is no way to make the final $S$ equal $T$, print `-1`."},{"iden":"constraints","content":"*   $T$ is a string consisting of lowercase English letters with length between $1$ and $100$, inclusive.\n*   $N$ is an integer between $1$ and $100$, inclusive.\n*   $A_i$ is an integer between $1$ and $10$, inclusive.\n*   $S_{i,j}$ is a string consisting of lowercase English letters with length between $1$ and $10$, inclusive."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$N$\n$A_1$ $S_{1,1}$ $S_{1,2}$ $\\dots$ $S_{1,A_1}$\n$A_2$ $S_{2,1}$ $S_{2,2}$ $\\dots$ $S_{2,A_2}$\n$\\vdots$\n$A_N$ $S_{N,1}$ $S_{N,2}$ $\\dots$ $S_{N,A_N}$"},{"iden":"sample input 1","content":"abcde\n3\n3 ab abc abcd\n4 f c cd bcde\n2 e de"},{"iden":"sample output 1","content":"2\n\nFor example, doing the following makes the final $S$ equal $T$ with two yen, which can be shown to be the minimum amount required.\n\n*   For $i=1$, select `abc` from bag $1$ and concatenate it to the end of $S$, making $S=$ `abc`.\n*   For $i=2$, do nothing.\n*   For $i=3$, select `de` from bag $3$ and concatenate it to the end of $S$, making $S=$ `abcde`."},{"iden":"sample input 2","content":"abcde\n3\n2 ab abc\n3 f c bcde\n1 e"},{"iden":"sample output 2","content":"\\-1\n\nThere is no way to make the final $S$ equal $T$, so print `-1`."},{"iden":"sample input 3","content":"aaabbbbcccc\n6\n2 aa aaa\n2 dd ddd\n2 ab aabb\n4 bbaa bbbc bbb bbcc\n2 cc bcc\n3 ccc cccc ccccc"},{"iden":"sample output 3","content":"4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}