E. Stringforces
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Требуется заменить каждый знак вопрос на одну из первых $$$k$$$ строчных латинских букв таким образом, чтобы максимизировать следующее значение.

Пусть $$$f_i$$$ будет максимальной длиной подстроки строки $$$s$$$, которая состоит целиком из $$$i$$$-й латинской буквы. Подстрока строки — это некоторый ее непрерывный подотрезок. Если $$$i$$$-я буква не встречается в строке, то $$$f_i$$$ равно $$$0$$$.

Значение строки $$$s$$$ — это минимальное значение среди $$$f_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$k$$$.

Какое наибольшее значение может иметь строка?

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

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 17$$$) — длина строки и количество использованных первых латинских букв.

Во второй строке записана строка $$$s$$$, состоящая из $$$n$$$ символов. Каждый символ — это либо одна из первых $$$k$$$ строчных латинских букв, либо знак вопроса.

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

Выведите одно целое число — наибольшее значение, которое может иметь строка, если заменить каждый знак вопроса на одну из первых $$$k$$$ строчных латинских букв.

Примеры
Входные данные
10 2
a??ab????b
Выходные данные
4
Входные данные
9 4
?????????
Выходные данные
2
Входные данные
2 3
??
Выходные данные
0
Входные данные
15 3
??b?babbc??b?aa
Выходные данные
3
Входные данные
4 4
cabd
Выходные данные
1
Примечание

В первом примере знаки вопроса можно заменить следующим образом: «aaaababbbb». $$$f_1 = 4$$$, $$$f_2 = 4$$$, поэтому ответ равен $$$4$$$. Можно заменить и таким образом: «aaaabbbbbb». Тогда $$$f_1 = 4$$$, $$$f_2 = 6$$$, однако, минимум из них все еще равен $$$4$$$.

Во втором примере одна из возможных строк такая: «aabbccdda».

В третьем примере хотя бы одна буква не встретится в строке, поэтому минимум из значений $$$f_i$$$ всегда равен $$$0$$$.