Crisp String

题意翻译

**题意** 给一个由前$p$（$p<=17$）个小写字母构成的长度为$n$（$n<=100000$）的字符串，再给一个$p×p$的邻接矩阵$G$（保证$G_{ij}=G_{ji}$），若一个字符串的所有相邻的字符$i$和$j$（这里是指从$a$开始第$i$和第$j$个字母）满足$G_{ij}=1$，那么称这个字符串是“好的”（空串也是好的）。 你每次能够选择一种字符并把当前串内所有这个字符删去，但操作后的字符串必须还是好的。问最终能够得到的字符串的最小长度。 保证一开始的串是好的。

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

说明

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.