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

import copy
import bisect

def main(N, L):
    L.sort(reverse=True)

    triangles = 0

    for i, P in enumerate(L):
        Q_list = copy.copy(L)
        del Q_list[:i + 1]
        for j, Q in enumerate(Q_list):
            if Q < P / 2:
                break
            minR = P - Q + 1
            R_list = copy.copy(Q_list)
            del R_list[:j + 1]
            R_list.reverse()
            # print(R_list, minR, bisect.bisect_left(R_list, minR))
            triangles += len(R_list) - bisect.bisect_left(R_list, minR)

            # for R in R_list:
            #     if R >= minR:
            #         triangles += 1
            #     else:
            #         break

    print(triangles)

if __name__ == '__main__':
    N = int(input())
    L = list(map(int, input().split()))
    main(N, L)


### FIXED CODE ###

import copy
import bisect

N = int(input())
L = sorted(list(map(int, input().split())))

triangles = 0

for i in range(N - 2):
    P = L[i]
    for j in range(i + 1, N - 1):
        Q = L[j]
        if P + Q <= L[j + 1]:
            continue
        maxR = P + Q - 1
        triangles += bisect.bisect_right(L, maxR) - (j + 1)

print(triangles)
### BUGGY CODE ###

X = int(input())
diff = 1
for i in range(2,X):
    if X % i == 0:
        diff = i
        break

s = (10 **9 /diff)//2
while True:
    A = s 
    B = s - diff
    xx = A **5 - B ** 5
    if xx == X:
        break
    elif xx > X:
        s = s //2
    else:
        s = s + s //2
print(int(A),int(B))

### FIXED CODE ###

def main():
    X = int(input())
    for B in range(-120,121):
        for A in range(B,121):
            xx = A**5 -B ** 5
            if X ==  xx:
                print(A,B)
                return
            elif X <xx:
                break

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

from collections import deque
import numpy as np

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append("#" * W)
for h in range(H-2):
  grid.append("#" + input() + "#")
grid.append("#" * W)

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][w]=="#": continue

    dist = np.array([[INF]*W for i in range(H)])
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][n_w]=="#": continue
        d_v = dist[v_h][v_w]
        d_n = d_v + 1
        if (dist[n_h][n_w] == -1) & (d_n > dist[n_h][n_w]):
          continue
        
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))


    
      dist_m = max(x for x in dist.flatten() if x < INF)
      ans = max(ans, dist_m)

print(ans)

      


    

### FIXED CODE ###

from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        #初期化
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        #start位置は0で初期化
        distance[x][y] = 0
        ans = max(ans, np.max(distance))

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

def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
l=1
for a in A:
  l=lcd(l,a)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

### FIXED CODE ###

P=1000000007
def power(x,p):
  if(p==0):
    return 1;
  if(p%2):
    return power(x,p-1)*x%P;
  a=power(x,p//2);
  return a*a%P;
def inv(x):
  return power(x,P-2);
N=int(input());A=list(map(int,input().split()));
#N=10000;A=[1000000 for i in range(N)];
L=[0 for i in range(max(A)+1)]
for a in A:
  t=a;i=2;
  while(i**2<=a):
    c=0;
    while(t%i==0):
      t//=i;c+=1;
    L[i]=max(L[i],c)
    i+=1;
  if(t!=1):
    L[t]=max(L[t],1)
    
l=1;
for i in range(2,len(L)):
  l=l*power(i,L[i])%P;
b=0;
for a in A:
  b=(b+inv(a))%P
print(l*b%P)
### BUGGY CODE ###

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 _pf(s): return print(s, flush=True)

#  f = open('C_input.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))
#  print(A)
N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = [None if i not in A else 0 for i in range(0, N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
for i in range(2, N+1):
    # i段目までの通りを計算する
    if dp[i] == 0:
        # i段目が障害のときは0になっているので飛ばす
        continue
    
    dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in a:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

print(dp[-1])
### BUGGY CODE ###

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

for i in range(n-1):
    for j in range(i+1,n):
        if a[i]==a[j]:
            print("NO")
            exit()
print("YES")

### FIXED CODE ###

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

b=list(set(a))
if len(a)==len(b):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

def solve(N, A, S):
    dp = [set() for _ in range(N+1)]
    dp[N].add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            for v in dp[i+1]:
                dp[i].add(v)
                dp[i].add(v ^ A[i])
        else:
            if A[i] in dp[i+1]:
                dp[i] |= dp[i+1]
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1] == "1":
            ans[i] = 1
        else:
            ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def solve(N, A, S):
    dp = []
    for i in reversed(range(N)):
        x = A[i]
        for v in dp:
            x = min(x, v^x)
        if x > 0:
            if S[i] == "0":
                dp.append(x)
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

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

n,m=map(int,input().split())
l=[[]for i in range(m+1)]
par=[-1 for i in range(n)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(n):
    ll=[int(j) for j in input().split()[1:]]
    for j in ll:
        for k in l[j]:
            if root(i)!=root(k):
                connect(i,k)
        l[j].append(i)

for i in par:
    if -i==n:
        print("YES")
        exit()
print("NO")

### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
l=[]
for i in range(n):
    for j in input().split()[1:]:
        l.append((i,int(j)+n-1,1))
edge=np.array(l,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n+m,n+m))

_,ll=connected_components(graph)

if 1 in ll[:n]:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(j + 1)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        ans = D[b - 1][a - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(i):
            D[i][j] = min(D[i][j],
            D[max(i, a - 1)][min(i, a - 1)] + c + D[max(j, b - 1)][min(j, b - 1)],
            D[max(i, b - 1)][min(i, b - 1)] + c + D[max(j, a - 1)][min(j, a - 1)])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    def isTarget(p):
        for i in range(N2):
            if p[i] != i+1:
                return False
        return True

    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))





### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = Puzzle()
                v[:] = u[:]
                v.path = u.path
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))
### BUGGY CODE ###

def finite_automation_matcher(T, delta, m):
    n = len(T)
    q = 0
    for i in range(n):
        q = delta[q * 62 + con(T[i])]
        if q == m:
            print(i - m + 1)


def con(x):
    if 48 <= ord(x) <= 57:
        return ord(x) - 48
    elif 65 <= ord(x) <= 90:
        return ord(x) - 55
    else:
        return ord(x) - 61


def i_con(a):
    if 0 <= a <= 9:
        return chr(a + 48)
    elif 10 <= a <= 35:
        return chr(a + 55)
    else:
        return chr(a + 61)


def compute_transition_function(P):
    sigma = list(range(62))
    m = len(P)
    delta = [0 for _ in range(62 * (m+1))]
    for q in range(m + 1):
        for a in sigma:
            k = min(m + 1, q + 2)
            while True:
                k = k - 1
                # print(m, q, k, P[0:k])
                if is_suffix(P[0:k], P[0:q], i_con(a)):
                    break
            delta[q * 62 + a] = k
    # print(delta)
    return delta


def is_suffix(x, y, a):
    if len(x) == 0:
        return True
    if x[len(x) - 1] != a:
        return False
    for i in range(len(x) - 1):
        if x[i] != y[len(y) - len(x) + 1 + i]:
            return False
    return True


t = input()
p = input()
m = len(p)
delta = compute_transition_function(p)
finite_automation_matcher(t, delta, m)


### FIXED CODE ###

def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    list_ = []
    for m in range(0, M):
        tmp = [int(x) for x in input().split()]
        list_.append(tmp)

    for j in range(0, M):
        A.sort()
        count = 0
        while count < list_[j][0]:
            if A[count] > list_[j][1]:
                break
            A[count] = list_[j][1]
            count += 1

    print(sum(A))

if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappush, heappop, heapify

def main():
    N, M = map(int, input().split())
    A_card = [-int(x) for x in input().split()]

    change_list = []
    for i in range(M):
        B, C = [int(x) for x in input().split()]
        change_list.append(((-1) * C, B))

    hq = []
    for i in range(N):
        heappush(hq, (A_card[i], 1))

    for i in range(M):
        heappush(hq, change_list[i])

    result_sum = 0
    count = 0
    while True:
        if count == N:
            break
        tmp = heappop(hq)
        if count + tmp[1] <= N:
            result_sum += (tmp[0] * tmp[1])
            count += tmp[1]
        else:
            result_sum += (tmp[0] * (N - count))
            break

    print(result_sum * (-1))

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

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

if k > n-1:
  list1 = [n]*n
  a = list1

for q in range(k):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
      
  a[0] = b[0]
  for j in range(n-1):
    a[j+1] = a[j] + b[j+1]

print(*a)

### FIXED CODE ###

#%%time
from itertools import accumulate
import numpy as np
from numba import njit

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def loop1(a):
  #b = [0]*(n+1)
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
  #a = list(accumulate(b))
  #a = a[:-1]
   
  #if np.all(a == n):
   # break

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*(n-k+1)
r=1
for i in range(k):
    r=r*a[i]
ans[0]+=r
for i in range(1,n-k+1):
    ans[i]+=(ans[i-1]*a[i+k-1])//a[i-1]
    if ans[i]>ans[i-1]:
      print("Yes")
    else:
      print("No")

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n-k):
  if a[k+i]>a[i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

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


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append(x)
		else:	W.append( W[-1]+x )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

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


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0
### BUGGY CODE ###

s = input()
q_number = int(input())
reverse_flag = 1
for i in range(q_number):
  temp = input().split()
  if temp[0] == "1": 
    reverse_flag = reverse_flag * -1
  else:
    if int(temp[1])*reverse_flag == 1 or int(temp[1])*reverse_flag == -2:
      s = temp[2] + s
    else:
      s = s + temp[2]      
      
if reverse_flag == -1:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q_number = int(input())
reverse_flag = 1
head = ""
tail = ""
for i in range(q_number):
  temp = input().split()
  if temp[0] == "1": 
    reverse_flag = reverse_flag * -1
  else:
    headstails = int(temp[1])*reverse_flag 
    if headstails == 1 or headstails == -2:
      head = temp[2] + head
    else:
      tail = tail + temp[2]
      
if reverse_flag == 1:
  print(head+s+tail)
else:
  print(tail[::-1]+s[::-1]+head[::-1])
### BUGGY CODE ###

from itertools import permutations
N,M,R=map(int,input().split())
r = [int(i) for i in input().split()]
inf=10**10
#[k][j][i]
dp=[[[inf]*N for i in range(N)]for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    dp[0][a-1][b-1]=c
    dp[0][b-1][a-1]=c
for k in range(1,N+1):
    for j in range(N):
        for i in range(N):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])

ans =inf
for elem in permutations(r, R):
    dis=0
    for i in range(R-1):
        dis+=dp[N][elem[i+1]-1][elem[i]-1]
    ans=min(ans,dis)
print(ans)


### FIXED CODE ###

from itertools import permutations
N,M,R=map(int,input().split())
r = [int(i) for i in input().split()]
inf=10**10
#[k][j][i]
dp=[[[inf]*N for i in range(N)]for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    dp[0][a-1][b-1]=c
    dp[0][b-1][a-1]=c
for k in range(1,N+1):
    for j in range(N):
        for i in range(N):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])

ans =inf
for elem in permutations(r, R):
    dis=0
    for i in range(R-1):
        dis+=dp[N][elem[i+1]-1][elem[i]-1]
    ans=min(ans,dis)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())

S = input()
n = list(map(int, str(S)))
count = 1
mas = []
for i in range(N-1):
    if n[i] == n[i + 1]:
        count += 1
        if i == N-2:
            mas.append(count)
    else:
        mas.append(count)
        count = 1
        if i == N-2:
            mas.append(1)
        

mas2 = []
if n[0] == 0:
    mas.insert(0, 0)
    
if n[N-1] == 0:
    mas.append(0)
    
l=len(mas)
mas2=[0]
for i in range(1, 1+len(mas)):
    mas2.append(sum(mas[:i]))
    
if K >= (l-1)/2:
    print(N)
else:
    mas3 = []
    k = int(((l-1)/2)-K+1)
    for i in range(k):
        mas3.append(mas2[K*2 + 2*i+1]-mas2[0 + 2*i])
    print(max(mas3))
        

### FIXED CODE ###

from itertools import accumulate

N, K = map(int, input().split())

S = input()
n = list(map(int, str(S)))
count = 1
mas = []
for i in range(N-1):
    if n[i] == n[i + 1]:
        count += 1
        if i == N-2:
            mas.append(count)
    else:
        mas.append(count)
        count = 1
        if i == N-2:
            mas.append(1)
        

mas2 = []
if n[0] == 0:
    mas.insert(0, 0)
    
if n[N-1] == 0:
    mas.append(0)
    
l=len(mas)
mas2=[0] + list(accumulate(mas))
#for i in range(1, 1+len(mas)):
#    mas2.append(sum(mas[:i]))
    
if K >= (l-1)/2:
    print(N)
else:
    mas3 = []
    k = int(((l-1)/2)-K+1)
    for i in range(k):
        mas3.append(mas2[K*2 + 2*i+1]-mas2[0 + 2*i])
    print(max(mas3))
### BUGGY CODE ###

import collections

n = int(input())
s = input()
cnt = 0
for i in range(n)[::-1]:
  ch = s[i:]
  c = collections.Counter(ch)
  tmp_cnt = 1
  for k,v in c.items():
    if k != s[i]:
      tmp_cnt *= (v+1)
  cnt += tmp_cnt
print(cnt)

### FIXED CODE ###

import collections

n = int(input())
s = input()
cnt = 0
dictionary = {}

for i in range(n)[::-1]:
  if s[i] in dictionary.keys():
    dictionary[s[i]] += 1
  else:
    dictionary[s[i]] = 1
  ch = s[i:]
  tmp_cnt = 1
  for k,v in dictionary.items():
    if k != s[i]:
      tmp_cnt *= (v+1)
  cnt += tmp_cnt % (10**9+7)
print(cnt % (10**9+7))