{"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 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`.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc344_d","tags":[],"sample_group":[["abcde\n3\n3 ab abc abcd\n4 f c cd bcde\n2 e de","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`."],["abcde\n3\n2 ab abc\n3 f c bcde\n1 e","\\-1\n\nThere is no way to make the final $S$ equal $T$, so print `-1`."],["aaabbbbcccc\n6\n2 aa aaa\n2 dd ddd\n2 ab aabb\n4 bbaa bbbc bbb bbcc\n2 cc bcc\n3 ccc cccc ccccc","4"]],"created_at":"2026-03-03 11:01:14"}}