Harryxun/stf_run huggingface dataset:
from collections import defaultdict as dd
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    best = dd(int)
    for i, (wi, vi) in enumerate(izip(wis, vis)):
        if wi < w:
            best[(wi, i)] = max(best[(wi, i)], vi)
            rv = max(vi, rv)

    frontline = [(i, wis[i], vis[i]) for i in xrange(n - 1, -1, -1)]
    while frontline:
        last, cw, cv = frontline.pop()
        for i in xrange(last + 1, n):
            nw, nv = cw + wis[i], cv + vis[i]
            if nw <= w and best[(nw, i)] < nv:
                best[(nw, i)] = nv
                frontline.append((i, nw, nv))
                rv = max(rv, nv)

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print sol(n, w, wis, vis)



### FIXED CODE ###

def sol(t, tis):
    flow = 0
    ret = 0
    for ti in tis:
        ret += min(ti + t - flow, t)
        flow = ti + t

    return ret


if __name__ == "__main__":
    n, t = map(int, raw_input().strip().split())
    tis = map(int, raw_input().strip().split())
    print sol(t, tis)
def oneNum(N):
    answer = 0

    while(N > 0):
        if(N >= 9):
            answer = answer + 9
        else:
            answer = answer + N
        
        N = N // 10

    return answer

def twoNum(N):
    answer = 0

    strN = str(N)
    topN = int(strN[0])
    lenN = len(strN)

    answer = answer + oneNum(int(strN[1:])) + (topN - 1) * oneNum(int('9' * (lenN - 1)))

    N = int('9' * (lenN - 1))

    while(N >= 10):
        N = N // 10
        answer = answer + 9 * oneNum(N)

    return answer

def main():
    N = int(input())
    K = int(input())

    answer = 0

    if(K == 1):
        answer = oneNum(N)

    elif(K == 2):
        answer = twoNum(N)

    else:
        strN = str(N)
        topN = int(strN[0])
        lenN = len(strN)

        answer = answer + twoNum(int(strN[1:])) + (topN - 1) * twoNum(int('9' * (lenN - 1)))

        N = int('9' * (lenN - 1))

        while(N >= 100):
            N = N // 10
            answer = answer + 9 * twoNum(N)

    print(answer)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#https://atcoder.jp/contests/abc154/tasks/abc154_e

def oneNum(N):
    answer = 0

    while(N > 0):
        if(N >= 9):
            answer = answer + 9
        else:
            answer = answer + N
        
        N = N // 10

    return answer

def twoNum(N):
    answer = 0

    strN = str(N)
    topN = int(strN[0])
    lenN = len(strN)

    if(lenN != 1):
        answer = answer + oneNum(int(strN[1:])) + (topN - 1) * oneNum(int('9' * (lenN - 1)))
        N = int('9' * (lenN - 1))

    while(N >= 10):
        N = N // 10
        answer = answer + 9 * oneNum(N)

    return answer

def main():
    N = int(input())
    K = int(input())

    answer = 0

    if(K == 1):
        answer = oneNum(N)

    elif(K == 2):
        answer = twoNum(N)

    else:
        strN = str(N)
        topN = int(strN[0])
        lenN = len(strN)

        answer = answer + twoNum(int(strN[1:])) + (topN - 1) * twoNum(int('9' * (lenN - 1)))

        N = int('9' * (lenN - 1))

        while(N >= 100):
            N = N // 10
            answer = answer + 9 * twoNum(N)

    print(answer)

if __name__ == "__main__":
    main()
N = int(input())
X = input()

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで
one = [0]*N

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1
for i in range(N):
    if X[i] == "1":
        one[i] = c-1
    else:
        one[i] = c+1
#print(one)

b1 = bin_num = int(X, 2)

for i in range(N):
    if X[i] == "0":
        B1 = b1 + 2**(N-1-i)
    else:
        B1 = b1 - 2**(N-1-i)
    #print(B1)
    B2 = B1%one[i]
    x = format(B2, 'b')
    #print(x)
    S = len(str(x))

    c2 = 0
    for j in range(S):
        if x[j] == "1":
            c2 += 1

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

### FIXED CODE ###

N = int(input())
X = input()

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1

m1 = 0
p1 = 0

for i in range(N):
    if c != 1:
        if X[i] == "1":
            m1 += pow(2,N-1-i,c-1)
            m1 %= c-1
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1
    else:
        if X[i] == "1":
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1

for i in range(N):
    if c != 1: 
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            B2 = m1 - pow(2,N-1-i,c-1)
            B2 %= c-1
    else:
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            print(0)
            continue

    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])
a, b = input().split()

c = a + b
c = int(c)

cc = math.sqrt(c)


if cc%1 == 0:
    print("Yes")
    

else:
    print("No")


### FIXED CODE ###

a, b = input().split(" ")

a= int(a)
b= int(b)

c = a*b

if c%2 ==0:
    print("Even")
    
else:
    print("Odd")
n = int(input())
a = int(input())
print('Yes') if n%500 <= a print('No')

### FIXED CODE ###

n = int(input())
a = int(input())
print('Yes') if n%500 <= a else print('No')
from collections import defaultdict
N,M = list(map(int,input().split()))
price_howmany = defaultdict(int)
price_list = []
for _ in range(N):
    tmp = list(map(int,input().split()))
    price_howmany[tmp[0]] += tmp[1]
    price_list.append(tmp[0])
# price_list.sort(reverse=True)
price_list.sort()

price_howmany = dict(price_howmany)

def solve():
    price = 0
    many = 0
    global M
    # while M > 0:
        # low_price = min(price_howmany.keys())
        # low_price = price_list.pop()
        # many = min(M,price_howmany.pop(low_price))
        # price += many * low_price
        # M -= many
    for low_price in price_list:
        many = many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

# from collections import defaultdict
# N,M = list(map(int,input().split()))
# price_howmany = defaultdict(int)
import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()
price_howmany = {}
# price_list = []

price_set = set()
for _ in range(N):
    tmp = read_int()
    # if tmp[0] not in price_set:
        # price_list.append(tmp[0])
    price_set.add(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
# price_list.sort(reverse=True)
price_list = sorted(list(price_set))

# price_howmany = dict(price_howmany)

def solve():
    price = 0
    global M
    # while M > 0:
        # low_price = min(price_howmany.keys())
        # low_price = price_list.pop()
        # many = min(M,price_howmany.pop(low_price))
        # price += many * low_price
        # M -= many
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()
r = int(input())
print(2 * r * pi)


### FIXED CODE ###

from math import pi

r = int(input())
print(2 * r * pi)
a,b,c=map(int,input().split())
d,e,f=map(int,input().split())
ans="NO"
if a==f and b==e and c==d:
  ans="YES"
print(ans)


### FIXED CODE ###

a = input()
b = input()
if a[0]==b[2] and a[1]==b[1] and a[2]==b[0]:
  print("YES")
else:
  print("NO")
a = input()
l = a.split("")
b = l.index("0")
print(b+1)

### FIXED CODE ###

a=input()
l=a.split(" ")
b=l.index("0")
print(b+1)
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a, b, c, d, e, f = LI()

x = f // 100*a
y = f // 100*b

max_ = 0
for i in range(x + 1):
    for j in range(y + 1):
        if i == 0 and j == 0:
            continue
        E = min((i + j)*e, f-(100*i + 100*j))
        E -= min(E % c, E % d)
        if max_ < E / (i+j):
            max_ = E / (i+j)
            ans1 = (i + j) * 100 + E
            ans2 = E
print(ans1, ans2)

### FIXED CODE ###

#!/usr/bin/env python3
#ABC74 C

a,b,c,d,e,f = map(int,input().split())

s = f//(100*a)
t = f//(100*b)
u = f//c
v = f//d

concentration = 0
solution = 0
suger = 0
for A in range(s+1):
    for B in range(t+1):
        for C in range(u+1):
            for D in range(v+1):
                if 100*a*A + 100*b*B + c*C + d*D <= f:
                    if (a*A+b*B)*e >= (c*C + d*D):
                        if 100*a*A + 100*b*B + c*C + d*D != 0:
                            if concentration < (c*C + d*D)/(100*a*A + 100*b*B + c*C + d*D):
                                concentration = (c*C + d*D)/(100*a*A + 100*b*B + c*C + d*D)
                                solution = 100*a*A + 100*b*B + c*C + d*D
                                suger = c*C + d*D
if solution == 0:
    solution = 100*a
print(solution,suger)
a,b,x = map(int, input().split())
b_num = int(b//x)
a_num = int((a-1)//x)
ans = b_num - a_num
print(ans)
          


### FIXED CODE ###

a, b, c = input().split()
print(a[0]+b[0]+c[0])
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

n=input()
S=list(input().split())
for i in S:
    i=int(i)
S=quick_sort(S)
word=int(int(n)/2)
print(S)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)


### FIXED CODE ###

import numpy as np
n=input()
S=[]
for i in input().split():
    S.append(int(i))
S=np.array(S)
word=int(int(n)/2)
asa=S.argsort()
s=int(S[asa[word]])-int(S[asa[word-1]])
print(s)
x,n = map(int,input().split())
if n != 0:
    p = list(map(int,input().split()))

    num = []
    for i in range(1,100):
        num.append(abs(x-i))

    for i in range(n):
        num[p[i]-1] = 1000

    min = 1000
    ansnum = 0
    for i in range(len(num)):
        if min > num[i]:
            min = num[i]
            ansnum = i

    print(ansnum+1)
else:
    print(x)

### FIXED CODE ###

x,n = map(int,input().split())
if n != 0:
    p = list(map(int,input().split()))

    num = []
    for i in range(-49,150):
        num.append(abs(x-i))

    for i in range(n):
        num[p[i]+49] = 1000

    min = 1000
    ansnum = -49
    for i in range(len(num)):
        if min > num[i]:
            min = num[i]
            ansnum = i-50

    print(ansnum+1)
else:
    print(x)
import copy
N,K = list(map(int, input().split()))
 
A = list(map(int, input().split()))
 
count = [0]
Check = [0] * N
for i in range(K):
    count.append(A[count[-1]])
    print(count)
    if(Check[count[-1]] == 1):
        break
 
    Check[count[-1]] = 1
    i += 1
 
 
saisyo = count.index(count[-1]) + 1

if(K > saisyo):
    loop_kazu = len(count) - saisyo
    K_loop = K - saisyo
 
    ans_index = K_loop % loop_kazu
    ans = count[saisyo + ans_index] + 1
 
    print(ans)

else:
    print(count[K] + 1)
 

### FIXED CODE ###

import copy
N,K = list(map(int, input().split()))
 
A = list(map(int, input().split()))
 
count = [0]
Check = [0] * N
for i in range(K):
    count.append(A[count[-1]]-1)
#    print(count)
    if(Check[count[-1]-1] == 1):
        break
 
    Check[count[-1]-1] = 1
    i += 1
 
saisyo = count.index(count[-1]) + 1
#print(count,saisyo)
 
if(saisyo == len(count)):
    saisyo = 0
 
loop_kazu = len(count) - saisyo
 
if(K > loop_kazu):
    K_loop = K - saisyo
 
    ans_index = K_loop % loop_kazu
    ans = count[saisyo + ans_index] + 1
 
    print(ans)
 
else:
    print(count[K]+1)
dat =list(input().split())

for i in dat:
      i = int(i)

dat.sort(reverse=True)

asum = 0
bsum = 0

for i in range(len(dat)):
	if (i%2==0):
		asum = asum + dat[i]
	else:
		bsum=bsum + dat[i]
		
print(asum-bsum)

### FIXED CODE ###

n = int(input())
dat = list(input().split())

dat = list(map(int,dat))

dat.sort(reverse=True)

asum = 0
bsum = 0

for i in range(n):
	if i % 2 == 0:
		asum = asum + dat[i]
	else:
		bsum = bsum + dat[i]
		
print(asum-bsum)
all = input()
all = [int(num) for num in all]
if sum(all) >= 22:
    print('bust')
else:
    print('win')

### FIXED CODE ###

all = input()
all = all.split(' ')
all = [int(num) for num in all]
if sum(all) >= 22:
    print('bust')
else:
    print('win')
#!/usr/bin/env python3
import sys


def solve(N: int, Y: int):
    for i in range(2000+1):
        for j in range((2000+1)-i):
            k = Y-10000*i-5000*j
            if(k//1000 == N-i-j):
                print(i,j,k//1000)
                sys.exit()

    prnt(-1,-1,-1)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    Y = int(next(tokens))  # type: int
    solve(N, Y)

if __name__ == '__main__':
    main()


### FIXED CODE ###

## ABC 085C
## C - Otoshidama

import sys
n, y = (int(_) for _ in input().split())

for i in range(0,n+1):
    for j in range(0,n+1-i):
        if(10000*i+5000*j+1000*(n-i-j) == y):
            print(i,j,n-i-j)
            sys.exit()
                    
print('-1 -1 -1')
import sys
heights = sort([ int(h) for h in sys.stdin],reverce)
heights[0]
heights[1]
heights[2]

### FIXED CODE ###

import sys
heights = sorted([ int(h) for h in sys.stdin ], reverse=True)
print( heights[0] )
print( heights[1] )
print( heights[2] )
a,b = map(int,input())
if a*b%2 == 0:
    print('Even')
else:
    print('Odd')

### FIXED CODE ###

a,b = map(int,input().split())
if (a*b)%2 == 0:
    print('Even')
else:
    print('Odd')
N = input()

flag =0
if N[0] == "7":
  flag = 1
if N[1] == "7":
  flag = 1
if N[2] == "7":
  flag = 1
  
if flag = 1:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = input()
 
flag =0
if N[0] == "7":
  flag = 1
if N[1] == "7":
  flag = 1
if N[2] == "7":
  flag = 1
  
if flag == 1:
  print("Yes")
else:
  print("No")
_n = raw_input()
_a = [int(x) in x for raw_input.split()]

_flg = 1

while _flg:
    _flg = 0
    for i in reversed(range(1, _n)):
        if _a[i] < _a[i-1]:
            _a[i], _a[i-1] = _a[i-1], _a[i]
            _flg = 1

print(" ".join(_a))

### FIXED CODE ###

_n = int(raw_input())
_a = [int(x) for x in raw_input().split()]

_flg = 1
cnt = 0

while _flg:
    _flg = 0
    for i in reversed(range(1, _n)):
        if _a[i] < _a[i-1]:
            _a[i], _a[i-1] = _a[i-1], _a[i]
            cnt += 1
            _flg = 1

print(" ".join([str(x) for x in _a]))
print(cnt)
n = int(input())
k = int(input())
if n>=10:
    print(int(k))
else:
    print(int(k+(100*(10-n))))

### FIXED CODE ###

n,k = map(int,input().split())
if n >= 10:
    print(k)
else:
    print(k+(100*(10-n)))
N = int(input())
kekka = 0
for i in range(1:N+1):
    if len(str(i)) % 2 == 1:
        kekka += 1

print(kekka)

### FIXED CODE ###

N = int(input())
kekka = 0
for i in range(1,N+1):
    if len(str(i)) % 2 == 1:
        kekka += 1

print(kekka)
a = int(raw_input())
b = int(raw_input())

print = (a * b)(a*2 + b*2)

### FIXED CODE ###

a,b = map(int,raw_input().split())
print ("{0} {1}").format(a*b,2*a+2*b)
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

N = int(input())
ans = 1
for i in range(0,N):
    t = int(input())
    ans = int((ans * t) / gcd(ans, t))
print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

N = int(input())
ans = 1

for i in range(0,N):
    t = int(input())
    ans = t * ans // gcd(ans, t)

print(ans)
from decimal import Decimal

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


A = Decimal(a) ** (1 / 2) + Decimal(b) ** (1 / 2)
C = Decimal(c) ** (1 / 2)
if A < C:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

from decimal import Decimal

a, b, c = map(int, input().split())
k = Decimal(0.5)

A = Decimal(a) ** k + Decimal(b) ** k
C = Decimal(c) ** k
if A < C:
    print("Yes")
else:
    print("No")
import numpy as np,math,itertools
n=int(input())
a=int(input())
b=int(input())
if n==1:print("Hello World")
else:print(a+b)

### FIXED CODE ###

import numpy as np,math,itertools
n=int(input())
if n==1:print("Hello World")
else:
    a=int(input())
    b=int(input())
    print(a+b)
N = int(input())

while a*2 <= N:
    a = a*2

print(a)

### FIXED CODE ###

N = int(input())
a = 1

while a*2 <= N:
    a *= 2
print(a)
s = input()
if s = 'Sunny':
    print('Cloudy')
elif s = 'Cloudy':
    print('Rainy')
elif s = 'Rainy':
    print('Sunny')

### FIXED CODE ###

s = input()
if s == "Sunny":
    print('Cloudy')
elif s == 'Cloudy':
    print('Rainy')
elif s == 'Rainy':
    print('Sunny')
n = int(input())
a = list(map(int,input().split()))

i = 1
if 1 in a:
    while i in a:
    del a[:a.index(i)]
    i += 1
    print(n-i+1)
else:
    print(-1)

### FIXED CODE ###

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

for i in a:
    if k == i:
        k += 1

if k == 1:
    print(-1)
else:
    print(n-k+1)
num = input()
lst = list(map(int, num))
ele = lst[-1]
if ele==2 or ele==4 or ele==5 or ele==7 or ele==9:
  	print("hon")
elif ele==1 or ele==6 or ele==8:
 	print("pon")
elif ele==3
	print("bon")

### FIXED CODE ###

num = input()
lst = list(map(int, num))
ele = lst[-1]
if ele==2 or ele==4 or ele==5 or ele==7 or ele==9:
  	print("hon")
elif ele==0 or ele==1 or ele==6 or ele==8:
 	print("pon")
elif ele==3:
	print("bon")
import math
N, M = map(int, input().split())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])

    if arr == [] and n != 1:
        arr.append([n, 1])

    return arr


mod = 10**9 + 7


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル
for i in range(2, N*2 + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


primes = factorization(M)
# 何箇所に分けるか（cnt以下）,その中でどう分けるか（しきりをどこにおくか（振り分けられないものが出ると選べれないのとおなじになるので、cnt - 選んだ数））

ans = 1

for p, cnt in primes:
    tmp = cmb(N+cnt-1, N-1, mod)
    ans *= tmp
    ans %= mod

print(ans)


### FIXED CODE ###

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


mod = 10**9 + 7


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


primes = factorization(M)
# 何箇所に分けるか（cnt以下）,その中でどう分けるか（しきりをどこにおくか（振り分けられないものが出ると選べれないのとおなじになるので、cnt - 選んだ数））

if N == 1 or M == 1:
    print(1)
    exit(0)
ans = 1
for p, cnt in primes:
    tmp = 0
    for i in range(1, min(cnt, N)+1):
        tmp += cmb(N, i, mod) * cmb(cnt-1, i-1, mod)
        #print(tmp, p, cnt, i)
        tmp %= mod
    ans *= tmp
    ans %= mod

print(ans)
N = int(input())
H = int(input())
W = int(input())
 
ANS = (N-(H-1))(N-(W-1))
 
print(ANS)

### FIXED CODE ###

N = int(input())
H = int(input())
W = int(input())
 
ANS = (N-(H-1))*(N-(W-1))
 
print(ANS)
n,k = map(int, input().split())
s = input()
cnt = 0
init = (s[0]=='1')
h=[1]
h_cnt = 0

for i in range(1,n):
    if(s[i]!=s[i-1]):
        h_cnt+=1
        h.append(1)
    else:
        h[h_cnt]+=1

h_cnt+=1

zero_num = 0
ans = 0

if(init): #start with 1
    zero_num = h_cnt//2;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2+1])
        ans = sum_0
        h = h +[0]
        for j in range(0,zero_num-k): #j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

else: #start with 0
    zero_num = h_cnt//2 +1;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2])
        ans = sum_0
        h = [0] + h +[0]
        for j in range(0,zero_num-k): #j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
s = input()
cnt = 0
init = (s[0]=='1')
h=[1]
h_cnt = 0

for i in range(1,n):
    if(s[i]!=s[i-1]):
        h_cnt+=1
        h.append(1)
    else:
        h[h_cnt]+=1

h_cnt+=1

zero_num = 0
ans = 0

if(init): #start with 1
    zero_num = h_cnt//2;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2+1])
        ans = sum_0
        h = h +[0,0,0]
        for j in range(0,zero_num-k): #j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

else: #start with 0
    zero_num = h_cnt//2 +1;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2])
        ans = sum_0
        h = [0] + h +[0,0,0]
        for j in range(0,zero_num-k):#j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

print(ans)
from math import gcd

N = int(input())
T = [int(input()) for i in range(N)]
ans = T[0]
def lcm(a, b):
    g = gcd(a, b)
    return a * b // g

for i in range(1, N):
    ans = lcm(ans, T[i])
print(ans)


### FIXED CODE ###

from fractions import gcd

N = int(input())
T = [int(input()) for i in range(N)]
ans = T[0]
def lcm(a, b):
    g = gcd(a, b)
    return a * b // g

for i in range(1, N):
    ans = lcm(ans, T[i])
print(ans)
def d_WideFlip(S):
    n = len(S)
    T = []  # 解説pdfにおけるT(S)の定義と同じもの
    for k in range(n - 1):
        if S[k] != S[k + 1]:
            T.append(max(k + 1, n - (k + 1)))  # 設問の文字列は1-indexedのため
    T = min(T)
    return T

S = input()
print(d_WideFlip(S))

### FIXED CODE ###

def d_WideFlip(S):
    n = len(S)
    T = []  # 解説pdfにおけるT(S)の定義と同じもの
    for k in range(n - 1):
        if S[k] != S[k + 1]:
            T.append(max(k + 1, n - (k + 1)))  # 設問の文字列は1-indexedのため
    if len(T) > 0:
        return min(T)
    else:
        return n  # Sは0のみまたは1のみで構成されていた

S = input()
print(d_WideFlip(S))
mport sys

for i in sys.stdin.readlines():
    a, b, c, d, e, f = [int(x) for x in i.split()]
    y = (c * d - a * f) / (b * d - a * e)
    x = (c - b * y) / a
    print('{0:.3f} {1:.3f}'.format(x, y))

### FIXED CODE ###

import sys

for i in sys.stdin.readlines():
    a, b, c, d, e, f = [int(x) for x in i.split()]
    y = (c * d - a * f) / (b * d - a * e)
    x = (c - b * y) / a
    print('{0:.3f} {1:.3f}'.format(x, y))