Stierlitz 想要向总部传递一条非常重要的消息 $s$。他使用了国家标准中定义的前缀码。不幸的是，敌人知道了这个编码，并且通信信道被窃听了。为了避免怀疑，Stierlitz 想要将密文分割成若干部分，使得每一部分都不是该编码中任何字符串的有效编码。为了最大化安全性，Stierlitz 想要最大化他将密文分割成的部分数量。请找出这个最大部分数量，或者确定无法满足要求的分割方式。

输入格式

第一行包含一个整数 $k$ ($1 \le k \le 52$)：字母表的大小。可能的字符按 A-Za-z 的顺序从 1 到 52 编号，消息文本仅包含编号从 1 到 $k$ 的字符。

第二行包含一个非空字符串 $s$，长度不超过 $10^6$，由编号从 1 到 $k$ 的字符组成（参见上述编号规则）。

接下来的 $k$ 行包含按编号顺序排列的字母表字符的二进制编码。每个字符由长度不超过 $k$ 的非空 0 和 1 序列编码。保证没有任何字符的编码是另一个字符编码的前缀。

输出格式

输出一个整数：最大部分数量；如果无法将密文分割成满足要求的部分，则输出 -1。

样例

输入 1

3
CACB
011
1
001

输出 1

2

输入 2

3
ACBABCAACABCAACC
0
10
110

输出 2

-1

说明

在第一个样例中，编码后的文本看起来像 0010110011。将其分割成不是任何字符串有效编码的部分的唯一方法是 0 和 010110011。因此，答案是 2。

在第二个样例中，可以通过归纳法证明，任何以 0 结尾且没有连续三个 1 的字符串都是某个字符串的有效编码。编码文本的每个后缀都符合此标准，因此答案是 -1。