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 CPP):

Solution:
// Problem: E. Stringforces
// Contest: Codeforces - Educational Codeforces Round 111 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1550/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


// By AmmarDab3an - Aleppo University

#include "bits/stdc++.h"

using namespace std;

// #define int int64_t
// #define ll  int64_t

typedef unsigned int        uint;
typedef long long int       ll;
typedef unsigned long long  ull;
typedef pair<int, int>    pii;
typedef pair<ll, ll>      pll;
typedef pair<int, pii>    iii;
typedef pair<ll, pll>     lll;
typedef vector<int>       vi;
typedef vector<ll>        vl;
typedef vector<pii>       vpii;
typedef vector<pll>       vpll;

#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define freopenI freopen("input.txt", "r", stdin);
#define freopenO freopen("output.txt", "w", stdout);

const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double  PI = acos(-1);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rand(int x, int y) {
    return uniform_int_distribution<int>(x, y)(rng);
}

int mul(int a, int b){
	return (1ll * (a%MOD) * (b%MOD)) % MOD;
}
 
int add(int a, int b){
	return (1ll * (a%MOD) + (b%MOD) + MOD + MOD) % MOD;
}
 
int pow_exp(int n, int p){
	if(!p) return 1;
	if(p&1) return mul(n, pow_exp(n, p-1));
	int tmp = pow_exp(n, p/2);
	return mul(tmp, tmp);
}
 
const int  MAX = 2e5 + 10;
const int NMAX = 2e5 + 10;
const int MMAX = 2e5 + 10;
const int LOG_MAX = ceil(log2(double(NMAX)));
const int BLOCK = ceil(sqrt(double(NMAX)));

int n, k;
char str[NMAX];
int mem[1 << 17];
int pre[17][NMAX];

int go(int msk){
    
    if(!msk) return 0;
    
    int &ret = mem[msk];
    if(ret+1) return ret;
    
    int ans = INF;
    
    for(int i = 0; i < k; i++) if((msk>>i)&1) {
        
        int len = go(msk^(1<<i));
        
        if((len < n) && (pre[i][len] <= n)){
            ans = min(ans, pre[i][len]);
        }
    }
    
    return ret = ans;
}

int32_t main(){
    
    fastIO;
    
#ifdef LOCAL
    freopenI;
    freopenO;
#endif

    // freopen("name.in", "r", stdin);
    
    cin >> n >> k >> str;
    
    int l = 0;
    int r = n/k;
    
    int ans = -1;
    
    while(l <= r){
        
        int mid = (l+r)/2;
        
        for(int i = 0; i < k; i++){
            
            int mn = INF;
            int cnt = 0;
            
            for(int j = n-1; j >= 0; j--){
                
                if((str[j] == '?') || (str[j]-'a' == i)){
                    cnt++;
                }
                else{
                    cnt = 0;
                }    
                
                if(cnt >= mid){
                    mn = j+mid;
                }
                
                pre[i][j] = mn;
            }
        }
        
        memset(mem, -1, sizeof mem);
        
        if(go((1<<k)-1) <= n){
            ans = mid;
            l = mid+1;
        }
        else{
            r = mid-1;
        }
    }
    
    cout << ans << endl;
}