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:
// Author :: <Hitesh_Saini>
#include<bits/stdc++.h>
 
#define __speed() cin.tie(0)->sync_with_stdio(0), cin.exceptions(cin.failbit);
#define precision cout << fixed << setprecision(12);

#ifndef ONLINE_JUDGE
#define dbg(...) write(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

#define Yes(x) print((x) ? "Yes" : "No")
#define TC     int t; for (cin >> t; t--; )
 
#define f0(i, n)  for (int i = 0; i < (int)(n); i++)
#define f1(i, n)  for (int i = 1; i <=(int)(n); i++)
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
 
#define EB emplace_back
#define PB push_back

#define LB lower_bound
#define UB upper_bound

#define endl "\n"
#define S second
#define F first

using namespace std;
using mii = map<int, int>;
using pii = pair<int, int>;

using ll = int64_t;
using vi = vector<int>;
 
using vvi = vector<vi>;
using vl = vector<ll>;
 
const pair<int, int> DD[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int mod = 1e9 + 7, mxN = 2e5 + 5, INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
 


template <typename... T> void print(T... args) { ((cout << args << " "), ...), cout << endl; }
template <typename... T> void write(string vars, T... args) { cout << endl; cout << "["; cout << vars << " = "; string delim = ""; (..., (cout << delim << args, delim = ", ")); cout << "]"; cout << endl; }

template <typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& p) { in >> p.F >> p.S; return in; }
template <typename T1, typename T2> ostream& operator<<(ostream& ot, pair<T1, T2>& p) { ot << p.F << ' ' << p.S; return ot; }

template <typename T1, typename T2> bool cmax(T1& a, T2 b) { if (b > a) { a = b; return true; } return false; }
template <typename T1, typename T2> bool cmin(T1& a, T2 b) { if (b < a) { a = b; return true; } return false; }

template <typename T> istream& operator>>(istream& in, vector<T>& v) { for (T& x:v) in >> x; return in; }
template <typename T> ostream& operator<<(ostream& ot, vector<T>& v) { for (T& x:v) ot << x << ' '; return ot;}

template <typename T> ostream& operator<<(ostream& ot, multiset<T>& s) { for (T x : s) ot << x << ' '; return ot; }
template <typename T1, typename T2> ostream& operator<<(ostream& ot, map<T1, T2>& M) {for (auto& [x, y] : M) ot << "(" << x << " : " << y << ")" << endl; return ot; }

template <typename T> using pq = priority_queue<T, vector<T>, greater<T>>;

ll mod_pow(ll x, ll y){ll res = 1;x = x % mod;while(y>0){if(y&1)res = (res*x) % mod; y = y>>1;x = (x*x) % mod; }return res; }ll mod_inv ( ll n ){ll ans = mod_pow ( n , mod - 2 ) ;return ans ;}ll mul(ll a, ll b){a%=mod, b%=mod;return (a*b)%mod;}ll sub(ll a,ll b){a%=mod, b%=mod;return (a-b+mod)%mod;}ll add(ll a, ll b){a%=mod, b%=mod;return (a+b)%mod;}


#define random(a, b) uniform_int_distribution<int>(a, b)(rng) // random number [a, b]
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());







void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vvi streak(n + 1, vi(k)); // streak[pos]['x'] = longest possible streak of 'x' from pos
  for (int i = n - 1; i >= 0; i--)
    for (int j = 0; j < k; j++) 
      if (s[i] == j + 'a' or s[i] == '?') streak[i][j] = 1 + streak[i + 1][j];
      else streak[i][j] = 0;

  function<bool(int)> good = [&](int v) {
    vi dp(1 << k, INF);
    vvi nxt(n + 1, vi(k + 1, n + 1)); // nxt[pos]['x'] next position >= pos, for whick streak[position]['x'] >= v
    for (int i = n - 1; i >= 0; i--) {
      for (int j = 0; j < k; j++) {
        if (streak[i][j] >= v) nxt[i][j] = i;
        else nxt[i][j] = nxt[i + 1][j];
      } 
    }
    dp[0] = 0; // answer for every mask is INF initially
    for (int mask = 0; mask < (1 << k); mask++) {
      if (dp[mask] >= n) continue;
      for (int j = 0; j < k; j++) { // taking j-th character
        if (mask & (1 << j)) continue; // if j-th character is already taken, we are done here...
        int nx = nxt[dp[mask]][j] + v;
        cmin(dp[mask | (1 << j)], nx);
      }
    }
    // dbg(dp.back());
    return dp.back() <= n;
  };

  int L = 0, R = n + 1;
  while (R - L > 1) {
    int M = (L + R) / 2;
    if (good(M)) L = M;
    else R = M;
  }
  print(L);
}





int main() {

  precision __speed() solve(); return 0; 
  // precision __speed() int t, i; for (cin >> t, i = 1; i <= t; i++) cout << "Case #" << i << ": ", solve(); return 0;
}