P5855 "SWTR-3" Password

Little $\mathrm{A}$ found a treasure chest in a dense forest. The chest has a combination lock, but little $\mathrm{A}$ does not know the password.

The password of the chest consists of $n$ digits. If you write them together, it can be seen as a string of length $n$. Little $\mathrm{A}$ wants to guess the password. For each digit position, there is a set $s_i$, representing the range of digits little $\mathrm{A}$ will try for the $i$-th position. Also, little $\mathrm{A}$ has already tried $k$ password strings $d_1,d_2,\dots,d_k$. **These passwords do not necessarily satisfy the above “try ranges”.** Little $\mathrm{A}$ wants to know the maximum number of additional attempts he may still need to crack the chest’s password. If he can never crack it, output $\mathrm{-1}$.

The first line contains two integers $n,k$. The second line contains a string $a$ of length $n$, representing the chest’s password. In the next $n$ lines, each line starts with an integer $v_i$, indicating the size of $s_i$, followed by a string $s_i$ of length $v_i$. It is guaranteed that all digits in $s_i$ are distinct. In the next $k$ lines, each line contains a **distinct** string $d_i$ of length $n$, indicating the password strings that little $\mathrm{A}$ has already tried.

Output the maximum number of additional attempts little $\mathrm{A}$ may still need to crack the chest’s password. If he can never crack it, output $-1$.

--- ### Sample Explanation - In sample $1$, the possible password strings little $\mathrm{A}$ may try are: `014,015,044,045,094,095,114,115,144,145,194,195`, a total of $12$ strings. This set contains the real password, but since `145` has already been tried, little $\mathrm{A}$ may need at most $11$ more attempts. - In sample $2$, the possible password strings little $\mathrm{A}$ may try are: `13,14,23,24`, a total of $4$ strings. None of them is the real password, so little $\mathrm{A}$ can never crack the password. --- ### Constraints and Notes **This problem uses bundled testdata.** Subtask ID | $n\leq$ | Special Property | Score :-: | :-: | :-: | :-: $1$ | $18$ | The answer is $-1$ | $7$ $2$ | $1$ | None | $13$ $3$ | $6$ | None | $24$ $4$ | $18$ | $k=0$ | $21$ $5$ | $18$ | None | $35$ For $100\%$ of the data, $1\leq n\leq 18$ and $0\leq k \leq\min(10^n-1,10^4)$. It is guaranteed that $d_i$ is not the password. --- For all test points, the time limit is $1\mathrm{s}$ and the memory limit is $128\mathrm{MB}$. Translated by ChatGPT 5