Problem: You are given a string s of length n. Each character is either one of the first k lowercase Latin letters or a question mark.

You are asked to replace every question mark with one of the first k lowercase Latin letters in such a way that the following value is maximized.

Let f_i be the maximum length substring of string s, which consists entirely of the i-th Latin letter. A substring of a string is a contiguous subsequence of that string. If the i-th letter doesn't appear in a string, then f_i is equal to 0.

The value of a string s is the minimum value among f_i for all i from 1 to k.

What is the maximum value the string can have?

Input

The first line contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ k ≤ 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.

Examples

Input


10 2
a??ab????b


Output


4


Input


9 4
?????????


Output


2


Input


2 3
??


Output


0


Input


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


Output


3


Input


4 4
cabd


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.

Solution (in JAVA):

Solution:
/*
Permission to Dance!
Hobi Luv
<3
 */
import static java.lang.Math.*;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1550E
{
    static final int INF = Integer.MAX_VALUE/5;
    public static void main(String hi[]) throws Exception
    {
        FastScanner infile = new FastScanner();
        int N = infile.nextInt();
        int K = infile.nextInt();
        char[] input = infile.nextLine().trim().toCharArray();
        int[] arr = new int[N];
        for(int i=0; i < N; i++)
        {
            if(input[i] == '?')
                arr[i] = -1;
            else
                arr[i] = input[i]-'a';
        }
        //print(arr);
        int low = 0;
        int high = N/K;
        while(low != high)
        {
            int mid = (low+high+1)>>1;
            int[][] right = new int[K][N];
            for(int c=0; c < K; c++)
            {
                Arrays.fill(right[c], INF);
                int tot = 0;
                for(int i=0; i < mid; i++)
                    if(arr[i] == c || arr[i] == -1)
                        tot++;
                if(tot == mid)
                    right[c][0] = mid;
                for(int i=mid; i < N; i++)
                {
                    if(arr[i-mid] == c || arr[i-mid] == -1)
                        tot--;
                    if(arr[i] == c || arr[i] == -1)
                        tot++;
                    if(tot == mid)
                        right[c][i-mid+1] = i+1;
                }
                for(int i=N-2; i >= 0; i--)
                    right[c][i] = min(right[c][i], right[c][i+1]);
            }
            int[] dp = new int[1<<K];
            Arrays.fill(dp, INF);
            dp[0] = 0;
            for(int mask=0; mask < 1<<K; mask++)
                if(dp[mask] < N)
                {
                    for(int b=0; b < K; b++)
                        if((mask&(1<<b)) == 0)
                        {
                            dp[mask|(1<<b)] = min(dp[mask|(1<<b)], right[b][dp[mask]]);
                        }
                }
            if(dp[(1<<K)-1] == INF)
                high = mid-1;
            else
                low = mid;
        }
        System.out.println(low);
    }
    public static void print(int[][] grid)
    {
        for(int r=0; r < grid.length; r++)
        {
            String lol = "";
            for(int c=0; c < grid[r].length; c++)
                lol += grid[r][c]+" ";
            System.out.println(lol);
        }
    }
    public static void print(int[] arr)
    {
        //for debugging only
        for(int x: arr)
            out.print(x+" ");
        out.println();
    }
}
/*
Binary search on answer (changing one character can yield answer = optimal-1)
For each i and letter k, find right[i][k] (leftmost index such that filling all ? from i to here will give a good substring)
dp[mask] = minimum index such that mask of letters have a good string
 */
class FastScanner
{
    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}