Given a string $s$ of length $n$ and integer $k$ ($1 \le k \le n$). The string $s$ has a level $x$, if $x$ is largest non-negative integer, such that it's possible to find in $s$:  $x$ non-intersecting (non-overlapping) substrings of length $k$,  all characters of these $x$ substrings are the same (i.e. each substring contains only one distinct character and this character is the same for all the substrings). 

A substring is a sequence of consecutive (adjacent) characters, it is defined by two integers $i$ and $j$ ($1 \le i \le j \le n$), denoted as $s[i \dots j]$ = "$s_{i}s_{i+1} \dots s_{j}$".

For example, if $k = 2$, then:  the string "aabb" has level $1$ (you can select substring "aa"),  the strings "zzzz" and "zzbzz" has level $2$ (you can select two non-intersecting substrings "zz" in each of them),  the strings "abed" and "aca" have level $0$ (you can't find at least one substring of the length $k=2$ containing the only distinct character). 

Zuhair gave you the integer $k$ and the string $s$ of length $n$. You need to find $x$, the level of the string $s$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string and the value of $k$.

The second line contains the string $s$ of length $n$ consisting only of lowercase Latin letters.


-----Output-----

Print a single integer $x$ — the level of the string.


-----Examples-----
Input
8 2
aaacaabb

Output
2

Input
2 1
ab

Output
1

Input
4 2
abab

Output
0



-----Note-----

In the first example, we can select $2$ non-intersecting substrings consisting of letter 'a': "(aa)ac(aa)bb", so the level is $2$.

In the second example, we can select either substring "a" or "b" to get the answer $1$.

Difficulty: interview

Starter code:

Solutions:
n, k = [int(i) for i in input().split()]

dic = dict()

s = list(input())

i = 0
while i<n:
    j = 1
    while i+j < n and s[i] == s[i+j]:
        j+=1
    if s[i] not in dic:
        dic[s[i]] = []
    dic[s[i]].append(j)
    i += j
ans = 0

for i in list(dic.keys()):
    ct = 0
    for j in dic[i]:
        ct+=(j//k)
    ans = max(ans, ct)
    #if min(dic[i]) >= k:
        #ans = max(ans, min(dic[i]))

print(ans)


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    s = S()
    t = ''
    d = collections.defaultdict(int)
    d[''] = 0
    b = 0
    for c in s:
        if t != c:
            b = 1
            t = c
        else:
            b += 1
        if b % k == 0:
            d[t] += 1

    return max(d.values())



print(main())



n, k = map(int, input().split())
s = input()

anslevel = 0

for c in range(ord('a'), ord('z') + 1):
    ch = chr(c)
    nowLen, level = 0, 0
    for i in s:
        if i == ch:
            nowLen += 1
            if nowLen == k:
                nowLen = 0
                level += 1
        else:
            nowLen = 0
    anslevel = max(anslevel, level)

print(anslevel)

from collections import Counter

n, k = list(map(int, input().split()))

s = input()

c = Counter()

p = ""
r = ""
for t in s:

    if t == p:
        r += t
    else:
        r = t

    if len(r) == k:
        c[r] += 1
        r = ""

    p = t

print(c.most_common(1)[0][1] if len(c) > 0 else 0)


n, k = list(map(int, input().split()))
s = input()
c = 'abcdefghijklmnopqrstuvwxyz'
ans = 0
for ch in c:
	lvl = 0
	count = 0
	for i in s:
		if i == ch:
			count += 1
			if count == k:
				count = 0
				lvl += 1
		else:
			count = 0
	if lvl > ans:
		ans = lvl
print(ans)


import itertools

n, k = list(map(int, input().split()))
s = input().strip()

resdict = {}
for c, g in itertools.groupby(s):
    count = len(list(g))
    if c not in resdict:
        resdict[c] = 0

    resdict[c] += count // k

print(max(resdict.values()))




import copy
import itertools
import string

###

def powmod(x, p, m):
	if p <= 0:
		return 1
	if p <= 1:
		return x%m
	return powmod(x*x%m, p//2, m) * (x%m)**(p%2) % m

###

def to_basex(num, x):
	while num > 0:
		yield num % x
		num //= x

def from_basex(it, x):
	ret = 0
	p = 1
	for d in it:
		ret += d*p
		p *= x
	return ret

###

def core():
	n,k = (int(x) for x in input().split())
	#print(n, k)
	s = input()
	
	ansd = {l : 0 for l in string.ascii_lowercase}
	for l in string.ascii_lowercase:
		cnt = 0
		for ch in s:
			if ch == l:
				cnt += 1
				if cnt >= k:
					ansd[l] += 1
					cnt = 0
			else:
				cnt = 0
	
	#print(ansd)
	
	ans = max(ansd.values())
	print(ans)


core()



































































































from collections import defaultdict as dd, deque

D = dd(list)

n,k = list(map(int,input().split()))
s = input()+'$'

last = None
l = 0
for c in s:
    if last != c:
        if l > 0:
            D[last].append(l)
            l = 0
    last = c
    l += 1

print(max(sum(x//k for x in D[d]) for d in D))



n, k = list(map(int, input().split()))
s = input() + '|'

prev = ''
d = {}

for c in s:
    if c == prev:
        d[c][-1] += 1

    else:
        d[c] = d.get(c, []) + [1]
    prev = c

res = 0
def f(l):
    return sum(e//k for e in l)
for l in list(d.values()):
    res = max(res, f(l))

print(res)


n,k=list(map(int,input().split()))
s=input()
d={}
i,j=0,0
while i<len(s):
	j=i
	while j<len(s) and s[j]==s[i]:
		j+=1
	ans=(j-i)//k
	if s[i] in d:
		d[s[i]]+=ans
	else:
		d[s[i]]=ans
	i=j
print(max(d.values()))


n,k = map(int,input().split())
s = input()
chars = {}
for c in s:
    chars[c]=1
s += '\0'
ans = 0
for c in chars:
    nowl = 0
    a = 0
    for d in s:
        if d == c:
            nowl+=1
        elif nowl>0:
            a += nowl//k
            nowl = 0
    ans = max(ans,a)
print(ans)

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n,k = li()
s = ns()

def run_length(s: str):
    ret = []
    buf = ""
    cnt = 0
    for si in s:
        if si != buf:
            if cnt > 0:
                ret.append([buf, cnt])
                
            buf = si
            cnt = 1
        else:
            cnt += 1
            
    ret.append([buf, cnt])
            
    return ret

ret = run_length(s)
        
dic = defaultdict(int)
for char, length in ret:
    dic[char] += length//k
    
ans = 0
for key, value in dic.items():
    ans = max(ans, value)
    
print(ans)

from sys import stdin
def kmp(pat, txt):
    leng = 0;i = 1
    ans=0
    M = len(pat) ;N = len(txt) ;lps = [0]*M ;j = 0
    #Calculo de lps, prefifo propio mas largo que tambien es sufijo de pat[0:i]
    while i < M:
        if pat[i]== pat[leng]:
            leng += 1
            lps[i] = leng
            i += 1
        elif leng != 0:
            leng = lps[leng-1] 
        else:
            lps[i] = 0
            i += 1
    i = 0 
    while i < N:

        if pat[j] == txt[i]: 
            i += 1;j += 1  
        if j == M:
            ans+=1
            i=i-j+len(pat)
            j =0
        elif i < N and pat[j] != txt[i]: 
            if j != 0: 
                j = lps[j-1] 
            else: 
                i += 1
    return ans
from sys import stdin
n,m=list(map(int,stdin.readline().strip().split()))
s=stdin.readline().strip()
ans=0
for i in range(26):
    ans=max(ans,kmp(chr(97+i)*m,s))
print(ans)


#! usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    n, k = list(map(int, input().split()))
    s = input()

    cnt = [0] * 26
    idx = 0
    while idx < n:
        cur = idx
        while cur < n - 1 and s[cur+1] == s[idx] and cur - idx + 1 < k:
            cur += 1

        if cur - idx + 1 == k:
            cnt[ord(s[idx]) - ord('a')] += 1
        idx = cur + 1

    print(max(cnt))


def __starting_point():
    main()

__starting_point()

l,k=map(int,input().split())
s=input()
c=[None]*26
for i in range(26):
    c[i]=[]
a=1
for i in range(1,l):
    if s[i]!=s[i-1]:
        c[ord(s[i-1])-ord('a')].append(a)
        a=1
    else:
        a+=1
c[ord(s[l-1]) - ord('a')].append(a)
ans=0
for i in range(26):
    cumm=0
    for j in c[i]:
        cumm+=j//k
    ans=max(ans,cumm)
print(ans)

from collections import defaultdict

n, k = list(map(int, input().split()))
a = defaultdict(int)
p = '@'
x = 0
for el in input():
    if el == p:
        x += 1
    elif p != '@':
        a[p] += (x + 1) // k
        x = 0
    p = el
if k != 0:
    a[p] += (x + 1) // k
print(max(a.values()))


n, k = map(int, input().split())
s = input()+'.'
a = [1 for i in range(n)]
d = {}

for i in range(1, n):
    if s[i] == s[i-1]:
        a[i] = a[i-1]+1
for i in range(n):
    if s[i] != s[i+1]:
        if s[i] in d:
            if a[i] in d[s[i]]:
                d[s[i]][a[i]] += 1
            else:
                d[s[i]][a[i]] = 1
        else:
            d[s[i]] = {}
            d[s[i]][a[i]] = 1
ans = 0
for c in d:
    tmpa = 0
    for size in d[c]:
        if size >= k:
            tmpa += (size//k)*d[c][size]
    ans = max(ans, tmpa)
print(ans)

n,k = list(map(int,input().split()))
s = input()
alph = "qwertyuiopasdfghjklzxcvbnm"
ti = [0] * 26
num = 1
for i in range(1,n):
    if s[i] == s[i-1]:
        num += 1
    else:
        if num >= k:
            ti[alph.find(s[i-1])] += num // k
        num = 1
if num >= k:
    ti[alph.find(s[-1])] += num // k
print(max(ti))


#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, K = getIntList()
#print(N)
S = input()

nc = ' '
sss = 'abcdefghijklmnopqrstuvwxyz'
dr = dict()
for c in sss:
    dr[c] = 0
tn = 0
for x in S:
    if x!=nc:
        nc = x
        tn = 1
    else:
        tn+=1
    if K==tn:
        dr[x] +=1
        tn = 0

r = max( dr.values())
print(r)





import sys
import math

def read_int():
	return int(input().strip())

def read_int_list():
	return list(map(int,input().strip().split()))

def read_string():
	return input().strip()

def read_string_list(delim=" "):
	return input().strip().split(delim)

###### Author : Samir Vyas #######
###### Write Code Below    #######

n,k = read_int_list()

s = read_string()

seen_distincts = {}
start = 0
while start < n-k+1:
	temp_dist = s[start]
	broken = 0
	broken_at = -1

	for i in range(1,k):
		if s[start+i] == temp_dist:
			pass
		else:
			broken = 1
			broken_at = start+i
			break

	if broken:
		start = broken_at
	else:
		seen_distincts[temp_dist] = seen_distincts.get(temp_dist,0) + 1
		start += k

maxi = 0
for k in seen_distincts:
	maxi = max(maxi,seen_distincts[k])

# print(seen_distincts)
print(maxi) 





n, k = [ int(a) for a in input().split() ]
s = input()

freq = {}
for c in 'abcdefghijklmnopqrstuvwxyz':
    freq[c] = 0

prev = '!'
run = 0
for x in s:
    if x == prev:
        run += 1
    else:
        prev = x
        run = 1

    if run == k:
        freq[x] += 1
        run = 0

print(max(freq.values()))



import sys

n, k = map(int, input().split())

s = input().strip()

last = ''
count = 0
ans = {}

for c in s:
    if c != last:
        if last not in ans.keys():
            ans[last] = 0
        ans[last] += count//k
        last = c
        count = 1
    else:
        count += 1
if last not in ans.keys():
    ans[last] = 0
ans[last] += count//k
count = 1

print(max(ans.values()))

n, k = input().split()
n, k = int(n), int(k)

s = input() + ' '

d = {}
prev = '!'
cont = 0

for char in s:
    #print(char, cont)
    if (char != prev) or (cont >= k):
        if (cont >= k):
            if (prev in d):
                d[prev] += 1
            else:
                d[prev] = 1
        
        prev = char
        cont = 1
    else:
        cont += 1

print(max(list(d.values()) + [0]))
    


n, k=(int(i) for i in input().split())
s=input()
D={}
for i in s:
    D[i]=[]
a=s[0]
c=1
for i in range(1, len(s)):
    if s[i]==a:
        c+=1
    else:
        D[a].append(c)
        a=s[i]
        c=1
D[a].append(c)
m=0
x=0
for i in list(D.keys()):
    for j in D[i]:
        x+=j//k
    if x>m: m=x
    x=0
print(m)