Problem Background

Little $\mathrm{A}$ found a treasure chest in a dense forest.

The chest is secured with a password lock, but Little $\mathrm{A}$ does not know the password.

Problem Description

The password of the chest consists of $n$ digits, which can be considered as a string of length $n$ when written together.

Little $\mathrm{A}$ wants to guess the password. For each digit, there is a set $s_i$ representing the range of guesses for the $i$-th digit.

Additionally, Little $\mathrm{A}$ has already tried $k$ password combinations $d_1, d_2, \dots, d_k$, which may not necessarily conform to the "guess range" mentioned above.

Little $\mathrm{A}$ wants to know the maximum number of attempts needed to guess the chest's password, or output $\mathrm{-1}$ if it is impossible to guess it.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains a string of length $n$, representing the chest's password.

The next $n$ lines, each starting with an integer $v_i$ representing the size of $s_i$, followed by a string of length $v_i$ which is $s_i$, ensuring that all digits in $s_i$ are unique.

The next $k$ lines, each containing a unique string of length $n$, representing the password combinations that Little $\mathrm{A}$ has already tried.

Output Format

Output the maximum number of attempts Little $\mathrm{A}$ needs to guess the chest's password, or $-1$ if it is impossible.

Sample Input and Output

Sample Input #1

3 2
094
2 01
3 149
2 45
145
345

Sample Output #1

11

Sample Input #2

2 1
12
2 12
2 34
13

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

153085

Sample Input #4

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

Sample Output #4

1468282385203195

Notes/Hints

Sample Explanation

• In Sample $1$, the possible password combinations Little $\mathrm{A}$ might try are: 014, 015, 044, 045, 094, 095, 114, 115, 144, 145, 194, 195 for a total of $12$ combinations, including the password. Since 145 has already been tried, Little $\mathrm{A}$ needs at most $11$ more attempts.

• In Sample $2$, the possible password combinations Little $\mathrm{A}$ might try are: 13, 14, 23, 24, totaling $4$ combinations, none of which is the password, so it is impossible for Little $\mathrm{A}$ to guess the password.

Data Range and Constraints

This problem uses batched testing.

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 cases, the time limit is $1\mathrm{s}$ and the memory limit is $128\mathrm{MB}$.

见题面 Input 部分

见题面 Output 部分