给你一个长度为 $$$n$$$ 的字符串。每个字符都是前 $$$p$$$ 小写拉丁字母之一。
您还得到一个矩阵 $$$A$$$,其二进制值的大小为 $$$p \times p$$$。该矩阵是对称的 ($$$A_{ij} = A_{ji}$$$)。 $$$A_{ij} = 1$$$ 表示字符串中可以有相邻的第 $$$i$$$ 和第 $$$j$$$ 拉丁字母。
如果字符串中的所有相邻字符都可以相邻(矩阵 $$$A$$$ 的相应单元格中有 1),我们称该字符串为“脆”。
你可以进行以下动作。选择任意字母,删除所有出现的字母,然后连接字符串的其余部分而不更改其顺序。例如,从“abacaba”中删除字母“a”将产生“bcb”。
给你的字符串很脆。每次移动后,琴弦都应保持清脆。
您可以进行任意数量的移动(可能为零)。您可以获得的最短结果字符串是多少?
输入
第一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le p \le 17$$$) — 初始字符串的长度和允许的拉丁字母前缀的长度。
第二行包含初始字符串。保证它只包含前 $$$p$$$ 小写拉丁字母,这样就很清晰。其中一些 $$$p$$$ 开头的拉丁字母可能不会出现在字符串中。
接下来的 $$$p$$$ 行包含 $$$p$$$ 整数 — 矩阵 $$$A$$$ ($$$0 \le A_{ij} \le 1$$$, $$$A_{ij} = A_{ji}$$$)。 $$$A_{ij} = 1$$$ 表示字符串中可以有相邻的第 $$$i$$$ 和第 $$$j$$$ 拉丁字母。
输出
打印一个整数 - 进行任意次数的移动(可能为零)后最短字符串的长度。
示例
输入 #1
7 3 abacaba 0 1 1 1 0 0 1 0 0
输出 #1
7
输入 #2
7 3 abacaba 1 1 1 1 0 0 1 0 0
输出 #2
0
输入 #3
7 4 bacadab 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0
输出 #3
5
输入#4
3 3 cbc 0 0 0 0 0 1 0 1 0
输出#4
0
注意
在第一个示例中,无法从初始字符串中删除任何字母。
在第二个示例中,您可以按顺序删除字母:“b”、“c”、“a”。中间步骤上的字符串将为:“abacaba”$$$\rightarrow$$$“aacaa”$$$\rightarrow$$$“aaaa”$$$\rightarrow$$$“”。
在第三个示例中,您可以删除字母“b”,仅此而已。
在第四个示例中,您可以按“c”、“b”的顺序删除字母,但不能按“b”、“c”的顺序删除字母,因为两个字母“c”不能相邻。