Background

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.

Problem Description

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}$.

Input Format

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 Format

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

3 2
094
2 01
3 149
2 45
145
345

11

2 1
12
2 12
2 34
13

-1

6 10
907887
9 295064731
6 796350
9 295378410
5 48520
9 745208361
7 8079632
111664
422880
521471
433649
037388
091076
235569
979229
268527
690028

153085

18 10
869813962161100526
7 1762348
8 13948756
6 542169
8 78314952
6 432601
9 697130845
8 16358709
8 95204367
8 24079563
6 145602
7 6231549
6 157096
8 62534170
5 82390
7 5396702
8 20536491
7 1438692
5 59261
396440170984129947
891187409797339137
626815840963841542
192230179244843846
148170753474901744
142718603216393332
486224779191226121
819116507635433912
879948053659796486
875405657525125039

1468282385203195

Hint

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.

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