← 返回题目列表

Codeforces · 1117/F

F. 清脆的字符串

中文机器翻译题面 查看原题

给你一个长度为 $$$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”不能相邻。