题目背景

小 $\mathrm{A}$ 在茂密的森林里找到了一个宝箱。

宝箱设有密码锁，但小 $\mathrm{A}$ 不知道密码。

题目描述

宝箱的密码由 $n$ 位数字组成，如果将它们连在一起写，就可以看作是一个长度为 $n$ 的字符串。

小 $\mathrm{A}$ 想通过猜的方式试出密码。对于每一位数字，都会有一个集合 $s_i$，表示小 $\mathrm{A}$ 第 $i$ 位的尝试范围。

同时，小 $\mathrm{A}$ 已经试过了 $k$ 个密码组合 $d_1,d_2,\dots,d_k$，这些密码不一定符合上文中的“尝试范围”。

小 $\mathrm{A}$ 想知道他最多还需要尝试多少次才可以试出宝箱的密码，如果永远试不出输出 $\mathrm{-1}$。

输入格式

第一行，两个整数 $n,k$。

第二行，一个长度为 $n$ 的字符串 $a$，表示宝箱的密码。

接下来 $n$ 行，每行以一个整数 $v_i$ 开头，表示 $s_i$ 的大小，接下来一个长度为 $v_i$ 的字符串 $s_i$，保证 $s_i$ 各位数字互不相同。

接下来 $k$ 行，每行一个互不相同的长度为 $n$ 的字符串 $d_i$，表示小 $\mathrm{A}$ 已经试过了哪些密码组合。

输出格式

输出小 $\mathrm{A}$ 最多还需要尝试多少次可以试出宝箱的密码，如果永远试不出，输出 $-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

提示

样例说明

• 在样例 $1$ 中，小 $\mathrm{A}$ 可能试的密码组合有：014,015,044,045,094,095,114,115,144,145,194,195 共 $12$ 个数，其中包含密码，但因为 145 已经试过，所以小 $\mathrm{A}$ 最多还需尝试 $11$ 次。

• 在样例 $2$ 中，小 $\mathrm{A}$ 可能试的密码组合有：13,14,23,24，共 $4$ 个数，其中没有密码，所以小 $\mathrm{A}$ 永远试不出密码。

数据范围与约定

本题使用捆绑测试。

对于 $100\%$ 的数据，有 $1\leq n\leq 18$，$0\leq k \leq\min(10^n-1,10^4)$。

保证 $d_i$ 不为密码。

对于所有测试点，时间限制 $1\mathrm{s}$，空间限制 $128\mathrm{MB}$。