F. Аккуратная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка длины $$$n$$$. Каждый ее символ — это одна из $$$p$$$ первых строчных латинских букв.

Также задана матрица $$$A$$$ из бинарных значений размера $$$p \times p$$$. Матрица симметрична ($$$A_{ij} = A_{ji}$$$). $$$A_{ij} = 1$$$ обозначает, что $$$i$$$-я и $$$j$$$-я латинские буквы могут быть соседями в строке.

Назовем строку аккуратной, если все соседние символы в ней могут быть соседями (имеют 1 в соответствующей ячейке матрицы $$$A$$$).

Разрешается делать следующую операцию. Выбрать некоторую букву, удалить все ее вхождения и соединить оставшиеся части строки, не меняя их порядок. Например, после удаления буквы 'a' из «abacaba» останется «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$$$-я латинские буквы могут быть соседями в строке.

Выходные данные

Выведите единственное целое число — длину самой короткой строки, которую можно получить, сделав произвольное количество операций (возможно ноль).

Примеры
Входные данные
7 3
abacaba
0 1 1
1 0 0
1 0 0
Выходные данные
7
Входные данные
7 3
abacaba
1 1 1
1 0 0
1 0 0
Выходные данные
0
Входные данные
7 4
bacadab
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
Выходные данные
5
Входные данные
3 3
cbc
0 0 0
0 0 1
0 1 0
Выходные данные
0
Примечание

В первом примере ни одна буква не может быть удалена из начальной строки.

Во втором примере можно удалять буквы в порядке 'b', 'c', 'a'. Строки на промежуточных шагах будут: "abacaba" $$$\rightarrow$$$ "aacaa" $$$\rightarrow$$$ "aaaa" $$$\rightarrow$$$ "".

В третьем примере можно удалить букву 'b', и все.

В четвертом примере можно удалять буквы в порядке 'c', 'b', но не в порядке 'b', 'c', так как две буквы 'c' не могут быть соседями.