Stringforces

Description:

Input:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 17$$$) — the length of the string and the number of first Latin letters used.

The second line contains a string $$$s$$$, consisting of $$$n$$$ characters. Each character is either one of the first $$$k$$$ lowercase Latin letters or a question mark.

Output:

Print a single integer — the maximum value of the string after every question mark is replaced with one of the first $$$k$$$ lowercase Latin letters.

Sample Input:

10 2
a??ab????b

Sample Output:

4

Sample Input:

9 4
?????????

Sample Output:

2

Sample Input:

2 3
??

Sample Output:

0

Sample Input:

15 3
??b?babbc??b?aa

Sample Output:

3

Sample Input:

4 4
cabd

Sample Output:

1

Note:

In the first example the question marks can be replaced in the following way: "aaaababbbb". $$$f_1 = 4$$$, $$$f_2 = 4$$$, thus the answer is $$$4$$$. Replacing it like this is also possible: "aaaabbbbbb". That way $$$f_1 = 4$$$, $$$f_2 = 6$$$, however, the minimum of them is still $$$4$$$.

In the second example one of the possible strings is "aabbccdda".

In the third example at least one letter won't appear in the string, thus, the minimum of values $$$f_i$$$ is always $$$0$$$.