CF1117F.Crisp String

You are given a string of length $n$. Each character is one of the first $p$ lowercase Latin letters.

You are also given a matrix $A$ with binary values of size $p \times p$. This matrix is symmetric ($A_{ij} = A_{ji}$). $A_{ij} = 1$ means that the string can have the $i$-th and $j$-th letters of Latin alphabet adjacent.

Let's call the string crisp if all of the adjacent characters in it can be adjacent (have 1 in the corresponding cell of matrix $A$).

You are allowed to do the following move. Choose any letter, remove all its occurrences and join the remaining parts of the string without changing their order. For example, removing letter 'a' from "abacaba" will yield "bcb".

The string you are given is crisp. The string should remain crisp after every move you make.

You are allowed to do arbitrary number of moves (possible zero). What is the shortest resulting string you can obtain?

给你一个长度为 $n$ 的字符串，其中每个字符都是前 $p$ 个小写拉丁字母之一。

同时给你一个大小为 $p \times p$ 的二进制矩阵 $A$。该矩阵是对称的（即 $A_{ij} = A_{ji}$）。当 $A_{ij} = 1$ 时，表示字符串中可以出现第 $i$ 个与第 $j$ 个拉丁字母相邻。

若字符串中所有相邻字符对均满足“在矩阵 $A$ 对应位置上的值为 1”，则称该字符串为清晰的（crisp）。

你被允许执行如下操作：任选一个字母，删除该字母在字符串中的所有出现，并将剩余部分按原有顺序拼接起来。例如，从字符串 "abacaba" 中删除字母 'a'，将得到 "bcb"。

你所给定的初始字符串是清晰的。并且，你所做的每一次操作后，所得字符串也必须保持清晰。

你可以执行任意次数的操作（包括零次）。问：你能得到的最短字符串长度是多少？

The first line contains two integers $n$ and $p$ ($1 \le n \le 10^5$, $1 \le p \le 17$) — the length of the initial string and the length of the allowed prefix of Latin alphabet.

The second line contains the initial string. It is guaranteed that it contains only first $p$ lowercase Latin letters and that is it crisp. Some of these $p$ first Latin letters might not be present in the string.

Each of the next $p$ lines contains $p$ integer numbers — the matrix $A$ ($0 \le A_{ij} \le 1$, $A_{ij} = A_{ji}$). $A_{ij} = 1$ means that the string can have the $i$-th and $j$-th letters of Latin alphabet adjacent.

第一行包含两个整数 $n$ 和 $p$（$1 \le n \le 10^5$，$1 \le p \le 17$）—— 分别表示初始字符串的长度以及允许使用的拉丁字母表前缀的长度。

第二行包含初始字符串。保证该字符串仅由拉丁字母表前 $p$ 个小写字母组成，且是“清晰的”（crisp）。这前 $p$ 个拉丁字母中，部分字母可能并未在字符串中出现。

接下来的 $p$ 行，每行包含 $p$ 个整数——构成矩阵 $A$（$0 \le A_{ij} \le 1$，且 $A_{ij} = A_{ji}$）。若 $A_{ij} = 1$，则表示字符串中可以出现拉丁字母表中第 $i$ 个字母与第 $j$ 个字母相邻。

Print a single integer — the length of the shortest string after you make arbitrary number of moves (possible zero).

输出一个整数——即经过任意次（可能为零次）操作后，最短字符串的长度。

In the first example no letter can be removed from the initial string.

In the second example you can remove letters in order: 'b', 'c', 'a'. The strings on the intermediate steps will be: "abacaba" $\rightarrow$ "aacaa" $\rightarrow$ "aaaa" $\rightarrow$ "".

In the third example you can remove letter 'b' and that's it.

In the fourth example you can remove letters in order 'c', 'b', but not in the order 'b', 'c' because two letters 'c' can't be adjacent.

在第一个例子中，无法从初始字符串中删除任何字母。

在第二个例子中，你可以按如下顺序删除字母：'b'、'c'、'a'。中间步骤的字符串依次为："abacaba" $\rightarrow$ "aacaa" $\rightarrow$ "aaaa" $\rightarrow$ ""。

在第三个例子中，你只需删除字母 'b' 即可。

在第四个例子中，你可以按 'c'、'b' 的顺序删除字母，但不能按 'b'、'c' 的顺序删除，因为两个字母 'c' 不能相邻。