Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

max_A=max(AB)[0]+h
DP=[float("inf")]*max_A
DP[0]=0

for i in range(h):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

Fixed submission:
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(n)]

length=h+max(AB)[0]
DP=[float("inf")]*length
DP[0]=0

for i in range(h):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

Fixed submission:
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))

Fixed submission:
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce


def lcm(x,y):
    return (x*y)//gcd(x,y)


def lcm_list(nums):
    return reduce(lcm,nums,1)

mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
num=lcm_list(A)
cnt=0
for i in A:
    cnt +=num//i
print(cnt%mod)

Fixed submission:
from fractions import gcd
from functools import reduce


def lcm(x,y):
    return (x*y)//gcd(x,y)


def lcm_list(nums):
    return reduce(lcm,nums,1)

mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
num=lcm_list(A)
cnt=0
for i in A:
    cnt +=num//i
print(cnt%mod)
Buggy python submission (verdict: Runtime Error):
import numpy as np
from functools import reduce


n,m=map(int,input().split())
A=list(map(lambda x: int(x)//2,input().split()))

lcm=np.lcm.reduce(np.array(A))
if any([i for i in range(n) if lcm%(A[i]*2)==0]):
    print(0);exit()

ans=m//(2*lcm)
print(ans if m//lcm==0 else ans+1)

Fixed submission:
import fractions
from functools import reduce


n, m = map(int, input().split())
A = list(set(map(int, input().split())))

hA = [a//2 for a in A]
lcm = 1
for a in hA:
    lcm = (lcm * a) // fractions.gcd(lcm, a)
    if lcm > m:
        print(0)
        break
else:
    for a in A:
        if lcm % a == 0:
            print(0)
            break
    else:
        if (m//lcm) % 2 == 0:
            print(m//lcm//2)
        else:
            print(m//lcm//2 + 1)

Buggy python submission (verdict: Runtime Error):
import fractions
from functools import reduce


n, m = map(int, input().split())
A = list(set(map(int, input().split())))

hA = [a//2 for a in A]
lcm = 1
for a in hA:
    lcm = (lcm * a) // fractions.gcd(lcm, a)
    if lcm > m:
        print(0)
        break
else:
    else:
        if (m//lcm) % 2 == 0:
            print(m//lcm//2)
        else:
            print(m//lcm//2 + 1)


Fixed submission:
import fractions
from functools import reduce


n, m = map(int, input().split())
A = list(set(map(int, input().split())))

hA = [a//2 for a in A]
lcm = 1
for a in hA:
    lcm = (lcm * a) // fractions.gcd(lcm, a)
    if lcm > m:
        print(0)
        break
else:
    for a in A:
        if lcm % a == 0:
            print(0)
            break
    else:
        if (m//lcm) % 2 == 0:
            print(m//lcm//2)
        else:
            print(m//lcm//2 + 1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
if n%2==1:print(0);exit()
A=0
add=10
while n>=add:
    A +=n//add
    add *=5
print(sum(A))

Fixed submission:
n=int(input())
if n%2==1:print(0);exit()
A=0
add=10
while n>=add:
    A +=n//add
    add *=5
print(A)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
A=np.array(A)

ans=0
for i in range(60):
    count_1=len([i for i in A if i%2==1])
    ans +=2**i*count_1*(n-count_1)
    A >>=1

print(ans%mod)

Fixed submission:
import numpy as np
mod=10**9+7
n=int(input())
A=np.array(list(map(int,input().split())))

ans=0

for i in range(60):
    cnt=np.count_nonzero(A&1)
    ans +=2**i*cnt*(n-cnt)
    A >>=1

print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))

ans=0

for i in range(60):
    cnt=len([i for i in range(n) if A[i]&1])
    ans +=2**i*cnt*(n-cnt)
    A=[A[i]>>1 for i in range(n)]

print(ans%(10**9+7))


Fixed submission:
import numpy as np
mod=10**9+7
n=int(input())
A=np.array(list(map(int,input().split())))

ans=0

for i in range(60):
    cnt=np.count_nonzero(A&1)
    ans +=2**i*cnt*(n-cnt)
    A >>=1

print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
def pairORSum(arr, n,mod=10**9+7):
    ans = 0  # Initialize result

    # Consider all pairs (arr[i], arr[j)
    # such that i < j
    for i in range(0, n):

        for j in range(i + 1, n):
            ans = ans + (arr[i] ^ arr[j])
            ans %=mod

    return ans


n=int(input())
A=list(map(int,input().split()))
print(pairORSum(A,n))

Fixed submission:
import numpy as np
mod=10**9+7
n=int(input())
A=np.array(list(map(int,input().split())))

ans=0

for i in range(60):
    cnt=np.count_nonzero(A&1)
    ans +=2**i*cnt*(n-cnt)
    A >>=1

print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(n):
    for j in range(i):
        cnt +=A[i]^A[j]
        cnt %=mod
print(cnt)

Fixed submission:
import numpy as np
mod=10**9+7
n=int(input())
A=np.array(list(map(int,input().split())))

ans=0

for i in range(60):
    cnt=np.count_nonzero(A&1)
    ans +=2**i*cnt*(n-cnt)
    A >>=1

print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
def DFS(word,N):
    if len(word)==3:A.add(word)
    if len(word)>3:return
    for i in range(N+1,n):
        DFS(word+s[i],i)


n=int(input())
s=input()
A=set()
for i in range(n):
    DFS(s[i],i)
print(len(A))

Fixed submission:
n=int(input())
a=input()
ans=0
for i in range(1000):
    i=str(i).zfill(3)
    x=a.find(i[0])
    y=a.find(i[1],x+1)
    z=a.find(i[2],y+1)
    if x!=-1 and y!=-1 and z!=-1:
        ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n=int(input())
D=list(map(int,input().split()))
D_count=sorted(Counter(D).items())
if D_count[0][0]!=0 or D_count[0][1]!=1:print(0);exit()
ans=1
for i in range(1,max(D)+1):
    ans *=D_count[i-1][1]**D_count[i][1]
    ans %=998244353
print(ans)

Fixed submission:
from collections import Counter
mod=998244353
n=int(input())
D=list(map(int,input().split()))
Count=Counter(D)
if Count[0]!=1 or D[0]!=0:print(0);exit()
ans=1
for i in range(1,max(Count)+1):
    ans *=Count[i-1]**Count[i]
    ans %=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
n,m=map(int,input().split())
item=list(map(int,input().split()))
for i in range(n):item[i]=item[i]*-1
for i in range(m):
    heapq.heapify(item)
    a=heapq.heappop(item)
    heapq.heappush(item,((-1*a)//2)*-1)

print(sum(item)*-1)

Fixed submission:
import heapq
n,m=map(int,input().split())
item=list(map(lambda x: -int(x),input().split()))
heapq.heapify(item)
for i in range(m):
    a=-heapq.heappop(item)
    a //=2
    heapq.heappush(item,-a)

print(-sum(item))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
item=list(map(int,input().split()))
for i in range(m):
    item=sorted(item)
    item[-1]=item[-1]//2

print(sum(item))

Fixed submission:
import heapq
n,m=map(int,input().split())
item=list(map(lambda x: -int(x),input().split()))
heapq.heapify(item)
for i in range(m):
    a=-heapq.heappop(item)
    a //=2
    heapq.heappush(item,-a)

print(-sum(item))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
item=list(map(int,input().split()))
while 1:
    if m==0:break
    else:
        add=item.index(max(item))
        item[add]=item[add]//2
        m -=1

print(sum(item))

Fixed submission:
import heapq
n,m=map(int,input().split())
item=list(map(lambda x: -int(x),input().split()))
heapq.heapify(item)
for i in range(m):
    a=-heapq.heappop(item)
    a //=2
    heapq.heappush(item,-a)

print(-sum(item))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=[i+1 for i in range(n)]
print(sum(A)-n)

Fixed submission:
n=int(input())
print((n-1)*(n-2)//2+(n-1))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
cnt=0
for i in range(n):
    cnt +=i
print(cnt)

Fixed submission:
n=int(input())
print((n-1)*(n-2)//2+(n-1))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from _bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>=num:
        ans +=m
    index=num
    
print(ans+index)

Fixed submission:
from collections import defaultdict
from bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>=num:
        ans +=m
    index=num

print(ans+index)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from _bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>num:
        ans +=m
    index=num
    
print(ans+index)

Fixed submission:
from collections import defaultdict
from bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>=num:
        ans +=m
    index=num

print(ans+index)
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(n)]
flag=0
for i in range(1,int(n**0.5)+1):
    for j in range(0,n,i):
        B[i-1] +=A[j]
C=[]
for i in range(int(n**0.5)+1):
    if B[i]%2==A[i] and B[i]%2==0:
        flag=1
    if B[i]%2==A[i] and B[i]%2!=0:
        C.append(i+1)
        flag=1

if flag:
    if len(C)==0:print(0);exit()
    print(1)
    print(*C)
else:print(-1)

Fixed submission:
n=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(n+1)]
C=[]
cnt=0
for i in range(1,n+1)[::-1]:
    sum_B=sum(B[j] for j in range(i,n+1,i))
    if sum_B%2!=A[i-1]:
        B[i]=1
        C.append(i)
        cnt +=1
print(cnt)
print(*[i for i in C[::-1]])

Buggy python submission (verdict: Runtime Error):
n=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(n)]
for i in range(1,int(n**0.5)+1):
    for j in range(0,n,i):
        B[i] +=A[j]

C=[]
for i in range(int(n**0.5)+1):
    if B[i]%2==A[i]:
        C.append(i+1)

if len(C)==0:print(0);exit()
print(1)
print(*C)

Fixed submission:
n=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(n+1)]
C=[]
cnt=0
for i in range(1,n+1)[::-1]:
    sum_B=sum(B[j] for j in range(i,n+1,i))
    if sum_B%2!=A[i-1]:
        B[i]=1
        C.append(i)
        cnt +=1
print(cnt)
print(*[i for i in C[::-1]])
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
n=int(input())
A=[int(input()) for _ in range(n)]

DP=[[A[0]]]
for i in range(1,n):
    num,flag=A[i],1
    for j in range(len(DP)):
        if DP[j][-1]<num:
            DP[j].append(num)
            flag=0
            break
    if flag:DP.append([num])
    DP=sorted(DP, key=lambda x:x[-1], reverse=True)
print(len(DP))

Fixed submission:
from bisect import bisect_right
n=int(input())
A=[int(input()) for _ in range(n)][::-1]

DP=[A[0]]
for i in range(1,n):
    num=A[i]
    if DP[-1]<=num:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print(len(DP))
Buggy python submission (verdict: Runtime Error):
n,a,b=map(int,input())
print(min(n*a,b))

Fixed submission:
n,a,b=map(int,input().split())
print(min(n*a,b))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from itertools import permutations
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
B=[(a[0]-b[0],a[1]-b[1]) for a,b in permutations(A,2)]
most=max(Counter(B).values())
print(n-most if n!=1 else 1)

Fixed submission:
from collections import Counter
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
Per=[(a[0]-b[0],a[1]-b[1]) for a in A for b in A if a!=b]
print(n-Counter(Per).most_common(1)[0][1] if n!=1 else 1)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
Per=[(a[0]-b[0],a[1]-b[1]) for a in A for b in A if a!=b]
print(n-Counter(Per).most_common(1)[0][1])

Fixed submission:
from collections import Counter
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
Per=[(a[0]-b[0],a[1]-b[1]) for a in A for b in A if a!=b]
print(n-Counter(Per).most_common(1)[0][1] if n!=1 else 1)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n=int(input())
A=deque(sorted(list(map(int,input().split()))))
B=[]
while len(A)!=2:
    x,y=A.popleft(),A.pop()
    A.append(x-y)
    B.append([x,y])
    A=sorted(A)

B.append([A[-1],A[0]])
print(A[-1]-A[0])
for i in B:
    print(*i)

Fixed submission:
n=int(input())
A=sorted(list(map(int,input().split())))

XY=[]
left,right=A[0],A[-1]
for i in range(1,n-1):
    num=A[i]
    if num<0:
        XY.append([right,num])
        right -=num
    else:
        XY.append([left,num])
        left -=num
XY.append([right,left])
print(right-left)
for x,y in XY:print(x,y)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))+[-1]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    if i in A:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

Fixed submission:
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))+[-1]
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i==A[j]:
        dp[i]=0
        j +=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])

print(dp[n]%1000000007)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i==A[j]:
        dp[i]=0
        j +=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])

print(dp[n]%1000000007)

Fixed submission:
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))+[-1]
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i==A[j]:
        dp[i]=0
        j +=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])

print(dp[n]%1000000007)
Buggy python submission (verdict: Runtime Error):
def DFS(num,pre):
    global point
    if color[num]=="white":
        A[num]=C.pop()
        point +=min(A[num],pre)
        color[num]="black"
        for i in tree[num]:
            DFS(i,A[num])


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))

color=["white" for _ in range(n+1)]
tree=[[] for _ in range(n+1)]
for a,b in AB:
    tree[a].append(b)
    tree[b].append(a)

A=[0 for _ in range(n+1)]
point=0
DFS(1,0)

print(point)
print(*A[1:])

Fixed submission:
import sys
sys.setrecursionlimit(10**6)


def DFS(num,pre):
    global point
    if color[num]=="white":
        ans[num]=C.pop()
        point +=min(ans[num],pre)
        color[num]="black"
        for i in T[num]:
            DFS(i,ans[num])


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
point=0
DFS(0,0)

print(point)
print(*ans)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)


def DFS(num):
    if color[num]=="white":
        ans[num]=C.pop()
        color[num]="black"
        for i in T[num]:
            DFS(i)


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
DFS(0)

point=0
color=["white" for _ in range(n)]
for i in range(1,n+1):
    if len(T[i])>0:
        color[i-1]="black"
        for j in T[i]:
            if color[j-1]=="white":
                point +=min(ans[i-1],ans[j-1])
                color[j-1]="black"

print(point)
print(*ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)


def DFS(num,pre):
    global point
    if color[num]=="white":
        ans[num]=C.pop()
        point +=min(ans[num],pre)
        color[num]="black"
        for i in T[num]:
            DFS(i,ans[num])


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
point=0
DFS(0,0)

print(point)
print(*ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
S=input()
if S[m]=="A":S[m]="a"
elif S[m]=="B":S[m]="b"
else:S[m]="c"
print(S)

Fixed submission:
N,K = map(int,input().split())
S = list(input())
if S[K-1] == 'A':
    S[K-1] = 'a'
elif S[K-1] == 'B':
    S[K-1] = 'b'
else:
    S[K-1] = 'c'
print(''.join(S))
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

ans=0
for i in range(0,n,2):
    ans=max(ans,sum(A[i:2*k+1+i]))
print(ans)

Fixed submission:
n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

A=deque(A)
if len(A)<=1:print(sum(A));exit()
ans=0
while len(A)>1:
    ans=max(ans,sum([A[i] for i in range(min(2*k+1,len(A)))]))
    A.popleft()
    A.popleft()
print(ans)

Fixed submission:
n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

A=deque(A)
if len(A)<=1:print(sum(A));exit()
ans=0
while len(A)>1:
    ans=max(ans,sum([A[i] for i in range(min(2*k+1,len(A)))]))
    A.popleft()
    A.popleft()
print(ans)

Fixed submission:
n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()+" "
A=[0]*(n+1)
cnt=0
for i in range(1,n+1):
    if s[i-1]+s[i]=="AC":
        cnt +=1
    A[i+1]=cnt

for i in range(q):
    l,r=map(int,input().split())
    print(A[r]-A[l])

Fixed submission:
n,q=map(int,input().split())
s=input()+"P"
A=[list(map(int,input().split())) for i in range(q)]
B=[0]*(n+1)
cnt=0
for i in range(1,n):
    if s[i-1]+s[i]=="AC":cnt +=1
    B[i+1]=cnt

for l,r in A:print(B[r]-B[l])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
A=[list(map(int,input().split())) for i in range(q)]
B=[0]*(n+1)
for i in range(n):
    t=s[i:]
    cnt=0
    for j in range(len(t)-1):
        if t[j]+t[j+1]=="AC":
            cnt +=1
    B[i+1]=cnt

for l,r in A:
    print(B[l]-B[r])

Fixed submission:
n,q=map(int,input().split())
s=input()+"P"
A=[list(map(int,input().split())) for i in range(q)]
B=[0]*(n+1)
cnt=0
for i in range(1,n):
    if s[i-1]+s[i]=="AC":cnt +=1
    B[i+1]=cnt

for l,r in A:print(B[r]-B[l])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
A=[list(map(int,input().split())) for i in range(q)]
for l,r in A:
    t=s[l-1:r]
    cnt=0
    for i in range(len(t)-1):
        if t[i]+t[i+1]=="AC":
            cnt +=1
    print(cnt)

Fixed submission:
n,q=map(int,input().split())
s=input()+"P"
A=[list(map(int,input().split())) for i in range(q)]
B=[0]*(n+1)
cnt=0
for i in range(1,n):
    if s[i-1]+s[i]=="AC":cnt +=1
    B[i+1]=cnt

for l,r in A:print(B[r]-B[l])