Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

MOD = 998244353
MAX = n+2

fact, inverse = [0]*(MAX), [0]*(MAX)
fact[0], inverse[0] = 1, 1
for i in range(1, MAX):
  fact[i] = (fact[i-1]*i)%MOD
  inverse[i] = pow(fact[i], MOD-2, MOD)

def mod_comb(n, r):
  if n<r or n==0: return 0
  if r==0: return 1
  return (((fact[n]*inverse[r])%MOD)*inverse[n-r])%MOD

ans = 0
for i in range(n+1):
  if (k-A*i)%B == 0:
    b = (k-A*i)//B
    if 0<=b<=n:
      ans = (ans+mod_comb(n, i)*mod_comb(n, b))%MOD

if ans==0:
  print(1)
else:
  print(ans)

### FIXED CODE ###

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

MOD = 998244353
MAX = n+2

fact, inverse = [0]*(MAX), [0]*(MAX)
fact[0], inverse[0] = 1, 1
for i in range(1, MAX):
  fact[i] = (fact[i-1]*i)%MOD
  inverse[i] = pow(fact[i], MOD-2, MOD)

def mod_comb(n, r):
  if n<r or n==0: return 0
  if r==0: return 1
  return (((fact[n]*inverse[r])%MOD)*inverse[n-r])%MOD

ans = 0
for i in range(n+1):
  if (k-A*i)%B == 0:
    b = (k-A*i)//B
    if 0<=b<=n:
      ans = (ans+mod_comb(n, i)*mod_comb(n, b))%MOD

if ans==0:
  print(1)
else:
  print(ans)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(n):
	A.append(int(input()))

for i in range(n):
	A1 = A.copy()
	del A1[i]
	print(max(A1))

### FIXED CODE ###

n = int(input())
A = []
for i in range(n):
	A.append(int(input()))
	
B = A.copy()
B.remove(max(B))

A_max = max(A)
B_max = max(B)

for i in range(n):
	if A[i] == A_max:
		print(B_max)
	else:
		print(A_max)
### BUGGY CODE ###

left = input()
q = int(input())
right = ""
flag = 0
for i in range(q) :
    t = input()
    if t == "1" :
        flag ^= 1
        continue
    t, f, c = t.split(" ")
    f = int(f)
    left = c*((flag+f)%2) + left
    right += c*((flag+f-1)%2)
if flag == 0 :
    print(left+right)
else :
    print(right[::-1]+left[::-1])

### FIXED CODE ###

right = input()
Q = int(input())
flag = 0b1
left = ""
for i in range(Q):
    q = input()
    if q == "1":
        flag ^= 1
        continue
    m,f,c = q.split(" ")
    f = int(f)
    left += c*(1-flag)*(f-1)
    right += c*flag*(f-1)
    left += c*flag*(2-f)
    right += c*(1-flag)*(2-f)
if flag == 1:
    print(left[::-1]+right)
else:
    print(right[::-1]+left)
### BUGGY CODE ###

import bisect

n = int(input())
*a, = sorted(map(int, input().split()))
*b, = sorted(map(int, input().split()))
*c, = sorted(map(int, input().split()))

ans = 0
for _c in c:
    i = bisect.bisect_left(b, _c)
    for j in range(i):
        ans += bisect.bisect_left(a, b[j])

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
*a, = sorted(map(int, input().split()))
*b, = sorted(map(int, input().split()))
*c, = sorted(map(int, input().split()))

ans = 0
for _b in b:
    aNum = bisect.bisect_left(a, _b)
    cNum = len(c) - bisect.bisect_right(c, _b)
    ans += aNum*cNum

print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
Xs=list(map(int,input().split()))


Xs.sort()
costs=[]

for i in range(M-1):
    costs.append(abs(int(Xs[i])-int(Xs[i+1])))

for i in range(N-1):
    if not costs:
        print(0)
        exit(0)
    costs.remove(max(costs))




print(sum(costs))

### FIXED CODE ###

N,M=map(int,input().split())
Xs=list(map(int,input().split()))


Xs.sort()
costs=[abs(Xs[i]-Xs[i+1]) for i in range(M-1)]
costs.sort(reverse=True)

for i in range(N-1):
    if not costs:
        print(0)
        exit(0)
    costs.pop(0)




print(sum(costs))
### BUGGY CODE ###

import numpy as np

def main(H, W, s_list):
    row_count = np.zeros((H, W))
    for i_row in range(H):
        i_col = 0
        j_col = 0
        s = s_list[i_row]
        while(i_col < W):
            char = s[i_col]
            j_col = i_col
            
            if char == '.':
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s[j_col]
                    if c == '#':
                        break

                row_count[i_row, i_col:j_col] = j_col - i_col
            i_col = j_col + 1


    col_count = np.zeros((H, W))
    for i_col in range(W):
        i_row = 0
        j_row = 0
        s_col = [s[i_col] for s in s_list]
        while(i_row < H):
            char = s_col[i_row]
            j_row = i_row
            if char == '.':
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_col[j_row]
                    if c == '#':
                        break
                
                col_count[i_row:j_row, i_col] = j_row - i_row
            i_row = j_row + 1
    print(int(np.max(row_count + col_count)) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)


### FIXED CODE ###


def main(H, W, s_list):
    row_count = [[0]*W for _ in range(H)]
    for i_row in range(H):
        i_col = 0
        j_col = 0
        s = s_list[i_row]
        while(i_col < W):
            char = s[i_col]
            j_col = i_col
            
            if char == '.':
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s[j_col]
                    if c == '#':
                        break
                
                for k in range(i_col, j_col):
                    row_count[i_row][k] = j_col - i_col
            i_col = j_col + 1


    col_count = [[0]*W for _ in range(H)]
    for i_col in range(W):
        i_row = 0
        j_row = 0
        s_col = [s[i_col] for s in s_list]
        while(i_row < H):
            char = s_col[i_row]
            j_row = i_row
            if char == '.':
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_col[j_row]
                    if c == '#':
                        break
                for k in range(i_row, j_row):
                    col_count[k][i_col] = j_row - i_row
            i_row = j_row + 1

    m = 0
    for i_row in range(H):
        for i_col in range(W):
            sumation = row_count[i_row][i_col] + col_count[i_row][i_col]
            if sumation > m:
                m = sumation
    print(int(m) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
m = 10**15
for i in range(min(l),max(l)+1):
  m = min(m,sum(abs(j-i) for j in l))
print(m)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
import statistics as st
m = int(st.median(l))
print(sum(abs(m-i) for i in l))
### BUGGY CODE ###

n = int(input())
m = n

exp = []
div = []
for i in range(2, int(n**(1/2))+2):
    cnt = 0
    if n%i == 0:
        div.append(n//i)
        while n%i == 0:
            cnt += 1
            n //= i
        exp.append(cnt)

for i in div:
    cnt = 0
    while n%i == 0:
        cnt += 1
        n //= i
    if cnt >= 1:
        exp.append(cnt)

if n == m and m > 1:
    exp.append(1)

opr = 0
for x in exp:
    opr += int((-1+(8*x+1)**(1/2))/2)

print(opr)

### FIXED CODE ###

n = int(input())
m = n

exp = []

cnt = 0
while n%2 == 0:
    cnt += 1
    n //= 2
if cnt > 0:
    exp.append(cnt)

i = 3
while i*i <= n:
    cnt = 0
    while n%i == 0:
        cnt += 1
        n //= i
    exp.append(cnt)
    i += 2

if n != 1:
    exp.append(1)

opr = 0
for x in exp:
    opr += int((-1+(8*x+1)**(1/2))/2)

print(opr)
### BUGGY CODE ###

from itertools import permutations 
h,w = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
a = [[int(i) for i in input().split()] for _ in range(h)]
ans = 0
lst = [int(i) for i in range(10) if i != 1]
mp = [0]*10

for i in lst:
    mp[i] = c[i][1]
    for j in range(1,9):
        for k in permutations(lst,j):
            newlst = list(k)
            cnt = c[i][newlst[0]]
            for l in range(j-1):
                cnt += c[newlst[l]][newlst[l+1]]
            cnt += c[newlst[-1]][1]
            if cnt < mp[i]:
                mp[i] = cnt

for i in range(h):
    for j in range(w):
        if abs(a[i][j]) != 1:
            ans += mp[a[i][j]]

print(ans)


### FIXED CODE ###

from itertools import permutations 
h,w = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
a = [[int(i) for i in input().split()] for _ in range(h)]
ans = 0
lst = [int(i) for i in range(10) if i != 1]
mp = [0]*10

for i in lst:
    mp[i] = c[i][1]
    for j in range(1,9):
        for k in permutations(lst,j):
            newlst = list(k)
            cnt = c[i][newlst[0]]
            for l in range(j-1):
                cnt += c[newlst[l]][newlst[l+1]]
            cnt += c[newlst[-1]][1]
            if cnt < mp[i]:
                mp[i] = cnt

for i in range(h):
    for j in range(w):
        if abs(a[i][j]) != 1:
            ans += mp[a[i][j]]

print(ans)
### BUGGY CODE ###

import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = np.array(list(map(int, input().split())))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True

    if not scp:
        print('not coprime')
        exit()

    pcheckl = np.full((10**6+1), 0)
    for n in nlist:
        pcheckl[n] = 1

    pcp = np.all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = np.array(list(map(int, input().split())))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True

    if not scp:
        print('not coprime')
        exit()

    pcheckl = [0] * (10**6+1)
    for n in nlist:
        pcheckl[n] = 1

    pcp = all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left


## 約数の列挙O(N)
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def solve(N: int, M: int):
    if M%N == 0:
        print(M//N)
        return

    max_answer = M//N
    divisors = divisor(M)
    divisors.sort()

    for m in range(max_answer,0,-1):
        index = bisect_left(divisors,m)

        if divisors[index] == m:
            print(m)
            return 

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left


## 約数の列挙O(N)
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def solve(N: int, M: int):
    if M%N == 0:
        print(M//N)
        return

    max_answer = M//N
    divisors = divisor(M)
    divisors.sort()

    index = bisect_left(divisors,max_answer)
    if index == 0:
        print(1)
        return 
    print(divisors[index-1])


    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

X = input()
if X[:len(X) // 2].count("S") == len(X) // 2:
    print(0)
    exit()
for i in range(10**5):
    note = X
    X = X.replace("ST","")
    if note == X:
        break
print(len(X))

### FIXED CODE ###

X = input()
stack = []
for e in X:
    if e == "S":
        stack.append(e)
    elif stack == []:
        stack.append(e)
    elif stack[-1] == "T":
        stack.append(e)
    elif stack[-1] == "S":
        stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

import queue
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
 
Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
BlackVis = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == "#" and not BlackVis[h][w]:
            Visited = [[False for w in range(W)] for h in range(H)]
            Visited[h][w] = True
            Q = queue.Queue()
            Q.put((h,w))
            Mult = 1
            Count = 0
            while not Q.empty():
                now = Q.get()
                for s in Search:
                    nh, nw = now[0] + s[0], now[1]+s[1]
                    if 0 <= nh < H and 0 <= nw < W:
                        if S[now[0]][now[1]] != S[nh][nw] and not Visited[nh][nw]:
                            Visited[nh][nw] = True
                            Q.put((nh, nw))
                            if S[nh][nw] == ".":
                                Count += 1
                            else:
                                BlackVis[nh][nw] = True
                                Mult += 1
            Total += Count * Mult 
print(Total)

### FIXED CODE ###

import queue
H, W = map(int, input().split())
S = [list(map(int, input().replace(".", "0").replace("#","1"))) for h in range(H)]

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            Color = ([1, 0] if S[h][w] == 0 else [0, 1])
            Q = queue.Queue()
            Q.put((h, w, S[h][w]))
            while not Q.empty():
                nh, nw, nc = Q.get()
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
                            nextc = S[nexth][nextw]
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw, nextc))
                            Color[nextc] += 1
            Total += Color[0] * Color[1]

print(Total)
### BUGGY CODE ###

N=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))
for i in range(N):
  if D[i] in T:
    T.remove(D[i])
    D[i]=0
    if len(T)==0:
      break
if len(T)==0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

from collections import Counter
N=int(input())
D=list(map(int,input().split()))
d=Counter(D)
M=int(input())
T=list(map(int,input().split()))
t=Counter(T)
ans="YES"
for k in list(t.keys()):
  if d[k]<t[k]:
    ans="NO"
    break
print(ans)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
from heapq import heappush,heappop
ans=[]
data=[(-A[-1]-B[-1]-C[-1],X-1,Y-1,Z-1)]
visited=set()
while len(ans)<K:
    now=heappop(data)
    if (now[1],now[2],now[3]) not in visited:
        ans.append(-1*now[0])
        visited|={(now[1],now[2],now[3])}
    if now[1]>0:
        nex=now[0]+A[now[1]]-A[now[1]-1]
        heappush(data,(nex,now[1]-1,now[2],now[3]))
    if now[2]>0:
        nex=now[0]+B[now[2]]-B[now[2]-1]
        heappush(data,(nex,now[1],now[2]-1,now[3]))
    if now[3]>0:
        nex=now[0]+C[now[3]]-C[now[3]-1]
        heappush(data,(nex,now[1],now[2],now[3]-1))
for i in range(K):
    print(ans[i])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
from heapq import heappush,heappop
ans=[]
data=[(-A[-1]-B[-1]-C[-1],X-1,Y-1,Z-1)]
visited={(X-1,Y-1,Z-1)}
while len(ans)<K:
    now=heappop(data)
    ans.append(-1*now[0])
    if now[1]>0 and (now[1]-1,now[2],now[3]) not in visited:
        nex=now[0]+A[now[1]]-A[now[1]-1]
        heappush(data,(nex,now[1]-1,now[2],now[3]))
        visited|={(now[1]-1,now[2],now[3])}
    if now[2]>0 and (now[1],now[2]-1,now[3]) not in visited:
        nex=now[0]+B[now[2]]-B[now[2]-1]
        heappush(data,(nex,now[1],now[2]-1,now[3]))
        visited|={(now[1],now[2]-1,now[3])}
    if now[3]>0 and (now[1],now[2],now[3]-1) not in visited:
        nex=now[0]+C[now[3]]-C[now[3]-1]
        heappush(data,(nex,now[1],now[2],now[3]-1))
        visited|={(now[1],now[2],now[3]-1)}
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)
for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)

### FIXED CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)
### BUGGY CODE ###

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    ki = 1
    while ki <= k:
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      ki += 1
      if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
        if dp[nx][ny] == -1:ki = k+1
        if dp[nx][ny] == 0:
          dp[nx][ny] = dp[p[0]][p[1]] + 1
          if (nx == x2) &( ny == y2):exit( print(dp[x2][y2]-1))
          heapq.heappush(que, (dp[nx][ny], [nx,ny]))
          

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)


### FIXED CODE ###

#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)
### BUGGY CODE ###

import re

def norm(s):
    s1 = list(map(len, re.split('0+', s)))
    s0 = list(map(len, re.split('1+', s)))
    if s0[0] == 0:
        s0.pop(0)
    if s0[-1] == 0:
        s0.pop(-1)
    return [s0,s1]

def solve(n, k, s):
    s0, s1 = norm(s)

    if len(s1) == 1:
        return(s1[0])

    if len(s0) <= k:
        return(sum(s0) + sum(s1))
    
    al = []
    mv = 0
    for s0_idx in range(0, len(s0) - k + 1):
        v = sum(s0[s0_idx:s0_idx+k]) + sum(s1[s0_idx:s0_idx+k+1])
        if mv < v:
            mv = v

    return mv


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



### FIXED CODE ###

import re

def norm(s):
    s1 = list(map(len, re.split('0+', s)))
    s0 = list(map(len, re.split('1+', s)))
    if s0[0] == 0:
        s0.pop(0)
    if s0[-1] == 0:
        s0.pop(-1)
    return [s0,s1]

def solve(n, k, s):
    s0, s1 = norm(s)

    if len(s1) == 1:
        return(s1[0])

    if len(s0) <= k:
        return n
    
    s0_sum = sum(s0[0:k])
    s1_sum = sum(s1[0:k+1])

    v = s0_sum + s1_sum
    mv = v
    
    for last_idx in range(0, len(s0) - k):
        # update
        v = (v - s0[last_idx] + s0[last_idx + k] -
             s1[last_idx] + s1[last_idx + k + 1])
        if mv < v:
            mv = v

    return mv


n, k = map(int,input().split())
s = input()
print(solve(n, k, s))
### BUGGY CODE ###

N = int(input())
S = input()
def dfs(start, used, n):
    count = 0
    used = used.copy()
    for i in range(start, len(S)):
        if len(used)+len(S)-i < n:
            break
        if S[i] in used:
            continue
        else:
            used.add(S[i])
            if len(used) == n:
                count += 1
            else:
                count += dfs(i+1, used, n)
            used.remove(S[i])
    return count
ans = 0
for i in range(N):
    ans += dfs(0, set(), i+1)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
count = [0]*26
for ch in S:
    count[ord(ch)-ord('a')] += 1
ans = 1
for i in count:
    if i != 0:
        ans *= i+1
print((ans-1)%(10**9+7))
### BUGGY CODE ###

from bisect import bisect_right
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
res = [A[0]]
for a in A[1:]:
    idx = bisect_right(res, a)
    if idx == len(res):
        res.append(a)
    else:
        if res[idx] == a:
            res.append(a)
        else:
            res[idx] = a
        res.sort()
print(len(res))
    


### FIXED CODE ###

from bisect import bisect_right, insort_right
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
res = [A[0]]
for a in A[1:]:
    idx = bisect_right(res, a)
    if idx == len(res):
        res.append(a)
    else:
        if res[idx] == a:
            insort_right(res, a)   
        else:
            res[idx] = a
print(len(res))