High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters 'a' and 'b' only.


-----Output-----

Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.


-----Examples-----
Input
4 2
abba

Output
4

Input
8 1
aabaabaa

Output
5



-----Note-----

In the first sample, Vasya can obtain both strings "aaaa" and "bbbb".

In the second sample, the optimal answer is obtained with the string "aaaaabaa" or with the string "aabaaaaa".

Difficulty: interview

Starter code:

Solutions:
n, k = map(int,input().split())
s = input()
maxi = 0
a = 0
b = 0
st = 0
for i in range(0, n):
    if s[i] == 'a': a += 1
    else: b+=1
    if min(a, b) > k:
        if s[st] == 'a': a-=1
        else: b-=1
        st += 1
    else: maxi += 1
print(maxi)

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

longest = 0

left, right = 0, 0
currb = 1 if s[0] == 'b' else 0
while True:
    while right < n and currb <= k:
        right += 1
        if right < n and s[right] == 'b':
            currb += 1
    longest = max(longest, right - left)
    if s[left] == 'b':
        currb -= 1
    left += 1
    if left == n or right == n:
        break

left, right = 0, 0
currb = 1 if s[0] == 'a' else 0
while True:
    while right < n and currb <= k:
        right += 1
        if right < n and s[right] == 'a':
            currb += 1
    longest = max(longest, right - left)
    if s[left] == 'a':
        currb -= 1
    left += 1
    if left == n or right == n:
        break

print(longest)


__author__ = 'Utena'
n,k=map(int,input().split())
s=['0']+list(input())
beauty=0
i=0
j=0
a=0
b=0
while i<n:
    i+=1
    if s[i]=='a':
        a+=1
    if s[i]=='b':
        b+=1
    while min(a,b)>k:
        j+=1
        if s[j]=='a':
            a-=1
        if s[j]=='b':
            b-=1
    if i-j>beauty:
        beauty=i-j
print(beauty)

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

l = r = 0
a = b = 0
ans = 0

while r < n :
    if a <= k or a == 0 or b <= k or b == 0:
        ans = max(ans, r - l)

        if S[r] == 'a' : a += 1
        else : b += 1
        r += 1
    else :
        if S[l] == 'a' : a -= 1
        else : b -= 1
        l += 1

    if a <= k or a == 0 or b <= k or b == 0:
        ans = max(ans, r - l)

print(ans)

def solve(n, k, l):
  ki = i= s = 0; po = 1
  for j in range(n):
    s+=(l[j]==0)
    while s>k: s-=(l[i]==0); i+=1
    if j-i>ki-po: po,ki=i,j
  return ki -po + 1
  
  
  
  
n, k = map(int,input().split())
s = input()
a1, a2 = [], []
for i in range(n):
  if s[i] == 'a':
    a1.append(1)
    a2.append(0)
  else:
    a1.append(0)
    a2.append(1)
print(max(solve(n, k, a1), solve(n, k, a2)))

n,k=map(int,input().split())
s=input()
k1=k
k2=k
a=b=ans=0
for i in range(n):
    if s[i]=='b': k1-=1  
    else: k2-=1;
    while k1<0:
        if s[a]=='b': k1+=1
        a+=1
    while k2<0:
        if s[b]=='a': k2+=1
        b+=1
    ans=max(ans,i-a+1,i-b+1)
print(ans)

def solve(n, k, l):
  ki = i = s = 0
  po = 1
  for j in range(n):
    s += (l[j] == 0)
    while s > k: s -= (l[i] == 0); i += 1
    if j - i > ki - po: po, ki = i, j
  return ki - po + 1
  
  
  
  
n, k = map(int,input().split())
s = input()
list1, list2 = [], []
for i in range(n):
  if s[i] == 'a':
    list1.append(1)
    list2.append(0)
  else:
    list1.append(0)
    list2.append(1)
print(max(solve(n, k, list1), solve(n, k, list2)))

n,t=map(int,input().split())
s=input()
l=0
k=0
ma=0
for r in range(n):
    if s[r]=='a':
        if r-l+1>ma: ma=r-l+1
    else:
        while k>=t:
            if s[l]=='b':
                k-=1
            l+=1
        if r-l+1>ma: ma=r-l+1
        k+=1
        k%=r-l+2
l=0
k=0
for r in range(n):
    if s[r]=='b':
        if r-l+1>ma: ma=r-l+1
    else:
        while k>=t:
            if s[l]=='a':
                k-=1
            l+=1
        if r-l+1>ma: ma=r-l+1
        k+=1
        k%=r-l+2
print(ma)

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

# to a
i = -1
j = 0
cur = 0

while i < j <= n:
	if j == n and i == n - 1:
		break

	while cur <= k and j < n:
		if cur == k and s[j] == 'b':
			break
		else:
			cur += (s[j] == 'b')
			j += 1

	res = max(res, j - i - 1)

	if k > 0:
		if cur < k and i < j - 1:
			i += 1
			cur -= (s[i] == 'b')

		while cur == k and i < j - 1:
			i += 1
			cur -= (s[i] == 'b')
	else:
		i = j
		j = i + 1
res = max(res, j - i - 1)

# to b
i = -1
j = 0
cur = 0

while i < j <= n:
	if j == n and i == n - 1:
		break

	while cur <= k and j < n:
		if cur == k and s[j] == 'a':
			break
		else:
			cur += (s[j] == 'a')
			j += 1

	res = max(res, j - i - 1)

	if k > 0:
		if cur < k and i < j - 1:
			i += 1
			cur -= (s[i] == 'a')
			
		while cur == k and i < j - 1:
			i += 1
			cur -= (s[i] == 'a')
	else:
		i = j
		j = i + 1
res = max(res, j - i - 1)


print(res)

n, k = list(map(int,input().split()))
s = input()
l = 0
r = 0
ans = 0
num = 0
i = 0
while i < n:
    r += 1
    if s[i] == "b":
        num += 1
        if num > k:
            ans = max(ans,i-l)
            while l < n and s[l] != "b":
                l += 1
            l += 1
            num -= 1
    i += 1
ans = max(ans,i-l)

l = 0
r = 0
num = 0
i = 0
while i < n:
    r += 1
    if s[i] == "a":
        num += 1
        if num > k:
            ans = max(ans,i-l)
            while l < n and s[l] != "a":
                l += 1
            l += 1
            num -= 1
    i += 1
ans = max(ans,i-l)

print(ans)


read = lambda: list(map(int, input().split()))
n, k = read()
s = input()
i = j = 0
cur = k
while cur and j < n:
    if s[j] == 'a':
        cur -= 1
    j += 1
while j < n and s[j] == 'b':
    j += 1
ans = j
while j < n:
    while i < n and s[i] == 'b':
        i += 1
    i += 1
    j += 1
    while j < n and s[j] == 'b':
        j += 1 
    ans = max(ans, j - i)
i = j = 0
cur = k
while cur and j < n:
    if s[j] == 'b':
        cur -= 1
    j += 1
while j < n and s[j] == 'a':
    j += 1
ans = max(ans, j)
while j < n:
    while i < n and s[i] == 'a':
        i += 1
    i += 1
    j += 1
    while j < n and s[j] == 'a':
        j += 1
    ans = max(ans, j - i)
print(ans)


def check(lengths, k, full_count_of_opposite):
    maxcount = 0
    count = 0
    start = 0
    cur_k = k
    for i, el in enumerate(lengths):
        if i % 2 == 0:
            # print("count adding", el)
            count += el
        else:
            # print("count removing", el)
            if cur_k - el >= 0:
                cur_k -= el
            else:
                maxcount = max(count, maxcount)
                # print("so we found", start, maxcount)
                cur_k -= el
                while start < i and cur_k < 0:
                    count -= lengths[start]
                    cur_k += lengths[start + 1]
                    start += 2
                if start > i:
                    # print("start > i")
                    cur_k = k
                    count = 0
    maxcount = max(count, maxcount)
    # print("maxcount", maxcount)
    result = maxcount + min(k, full_count_of_opposite)
    # print(result)
    return result


def maxsubsl(s, k):
    lengths = []
    prev = s[0]
    cnt = 0
    full_counts = [0, 0]
    for el in s:
        if el != prev:
            lengths.append(cnt)
            cnt = 0
        prev = el
        cnt += 1
        full_counts[len(lengths) % 2] += 1
    lengths.append(cnt)
    # print("lengths", lengths)
    # print("full_counts", full_counts)

    maxl = check(lengths, k, full_counts[1])
    if len(lengths) > 1:
        maxl = max(maxl, check(lengths[1:], k, full_counts[0]))
    return maxl

_, k = list(map(int, input().split()))
s = input()
print(maxsubsl(s, k))


s = input().split()
n, k = int(s[0]), int(s[1])
s = input()

ans = 0

k1 = k
i1 = -1
i2 = 0
while i1 < n - 1:
	i1 += 1
	if s[i1] == 'b':
		if k1 > 0:
			k1 -= 1
		else:
			while s[i2] != 'b':
				i2 += 1
			i2 += 1
			
	if ans < i1 - i2:
		ans = i1 - i2
		
k1 = k
i1 = -1
i2 = 0
while i1 < n - 1:
	i1 += 1
	if s[i1] == 'a':
		if k1 > 0:
			k1 -= 1
		else:
			while s[i2] != 'a':
				i2 += 1
			i2 += 1
	if ans < i1 - i2:
		ans = i1 - i2
		
print(ans + 1)

n, k = map(int, input().split())
s = input()
e, t = 0, 0
res = 0
for i in range(n):
    if s[i] == "b":
        t += 1
    while t > k and e < i:
        if s[e] == "b":
            t -= 1
        e += 1
    res = max(res, i - e + 1)
e, t = 0, 0
    
for i in range(n):
    if s[i] == "a":
        t += 1
    while t > k and e < i:
        if s[e] == "a":
            t -= 1
        e += 1
    res = max(res, i - e + 1)
    

print(res)


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


s=input()

a=0
b=0
p=0
ind=0

for i in range(n):

    if s[i] == 'a':
        a += 1
    else:
        b += 1

    if min(a, b) > k:
        if s[p] == 'a':
            a -= 1

        else:
            b-=1

        p += 1


    else:
        ind+=1


























print(ind)


                      
            



from sys import stdin

N,K = map(int,stdin.readline().split())

charArr = list(stdin.readline().strip())

#print(charArr)

bad=0
front=0
front2=0
back=len(charArr)
answer=K
while front < back:
    if(charArr[front]!='a'):
        bad+=1
    if(bad>K):
        while(front2<=front and charArr[front2]=='a'):
            front2+=1
        bad-=1
        front2+=1
    answer=max(answer,front-front2+1)

    front+=1
bad=0
front=0
front2=0
back=len(charArr)
while front < back:
    if(charArr[front]!='b'):
        bad+=1
    if(bad>K):
        while(front2<=front and charArr[front2]=='b'):
            front2+=1
        bad-=1
        front2+=1
    answer=max(answer,front-front2+1)

    front+=1

print(answer)

from sys import *
inp = lambda : stdin.readline()

def solve(x,s,n,k):
    ans,r,bal = 0,0,0
    for l in range(n):
        while r < n and (s[r] == x or bal < k):
            if s[r] != x: bal += 1
            r += 1
        ans = max(ans,r-l)
        if s[l] != x:
            bal -= 1
    return ans

def main():
    n,k = map(int,inp().split())
    s = inp()
    print(max(solve("a",s,n,k),solve("b",s,n,k)))

def __starting_point():
    main()
__starting_point()

n, k = list(map(int, input().split()))
s = input()
ansa = 0
a = 0
b = 0
starta = 0
for i in range(0, n):
    if(s[i] == 'a'):
        a += 1
    else:
        b += 1
    if(min(a, b) > k):
        if(s[starta] == 'a'):
            a -= 1
        else:
            b -= 1
        starta += 1
    else:
        ansa += 1
print(ansa);


le, ch = map(int, input().split())
st = input()
ca, cb, si, mx = [0] * 4
for x in st:
    if x == 'a':
        ca += 1
    else:
        cb += 1
    if min(ca, cb) > ch:
        if st[si] == 'a':
            ca -= 1
        else:
            cb -= 1
        si += 1
    else:
        mx += 1
print(mx)

def solve(k, s, c):
    p = [-1, len(s)]
    for i in range(len(s)):
        if s[i] == c:
            p += [i]
    p.sort()
    n = len(p)
    if n - k - 1 <= 0:
        return len(s)
    m = 0
    for i in range(n - k - 1):
        m = max(m, p[i + k + 1] - p[i])
    return m - 1

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

print(max(solve(k, s, 'a'), solve(k, s, 'b')))