Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

D=int(input())
C=[0]+list(map(int,input().split()))
S=[0]+[[0]+list(map(int,input().split())) for i in range(D)]
T=[0]+[int(input()) for i in range(D)]

ANS=0
LAST=[[0]*27 for i in range(D+1)]
for day in range(1,D+1):
    for j in range(1,27):
        LAST[day][j]=LAST[day-1][j]
    t=T[day]
    ANS+=S[day][t]
    LAST[day][t]=day

    for j in range(1,27):
        ANS-=C[j]*(day-LAST[day][j])

    #print(ANS)

M=int(input())
for tests in range(M):
    d,after_t=map(int,input().split())

    before_t=T[d]

    ANS+=S[d][after_t]-S[d][before_t]

    T[d]=after_t

    for day in range(d,D+1):
        if T[day]!=before_t:
            ANS+=C[before_t]*(day-LAST[day][before_t])
            LAST[day][before_t]=LAST[day-1][before_t]
            ANS-=C[before_t]*(day-LAST[day][before_t])
        else:
            break

    ANS+=C[after_t]*(d-LAST[d][after_t])
    LAST[d][after_t]=d

    for day in range(d+1,D+1):    
        if T[day]!=after_t:
            ANS+=C[after_t]*(day-LAST[day][after_t])
            LAST[day][after_t]=LAST[day-1][after_t]
            ANS-=C[after_t]*(day-LAST[day][after_t])

    print(ANS)
    


Fixed submission:
import sys
input = sys.stdin.readline

D=int(input())
C=[0]+list(map(int,input().split()))
S=[0]+[[0]+list(map(int,input().split())) for i in range(D)]
T=[0]+[int(input()) for i in range(D)]

ANS=0
LAST=[[0]*27 for i in range(D+1)]
for day in range(1,D+1):
    for j in range(1,27):
        LAST[day][j]=LAST[day-1][j]
    t=T[day]
    ANS+=S[day][t]
    LAST[day][t]=day

    for j in range(1,27):
        ANS-=C[j]*(day-LAST[day][j])

    #print(ANS)

M=int(input())
for tests in range(M):
    d,after_t=map(int,input().split())

    before_t=T[d]

    ANS+=S[d][after_t]-S[d][before_t]

    T[d]=after_t

    for day in range(d,D+1):
        if T[day]!=before_t:
            ANS+=C[before_t]*(day-LAST[day][before_t])
            LAST[day][before_t]=LAST[day-1][before_t]
            ANS-=C[before_t]*(day-LAST[day][before_t])
        else:
            break

    ANS+=C[after_t]*(d-LAST[d][after_t])
    LAST[d][after_t]=d

    for day in range(d+1,D+1):    
        if T[day]!=after_t:
            ANS+=C[after_t]*(day-LAST[day][after_t])
            LAST[day][after_t]=LAST[day-1][after_t]
            ANS-=C[after_t]*(day-LAST[day][after_t])

    print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N=int(input())

A=[i for i in range(10**7+1)]
B=[i for i in range(10**7+1)]

if N==1:
    print(1)
    sys.exit()

def main():
    ANS=0

    for i in range(2,N+1):
        if B[i]==1:
            ANS+=A[i]
            continue
        
        for j in range(i,10**7+1,i):

            count=0
            while B[j]%i==0:
                count+=1
                B[j]//=i
            A[j]*=count+1
        ANS+=A[i]

    print(ANS+1)
main()

Fixed submission:
def main(): 
    N=int(input())
    ANS=0
    for i in range(1,N+1):
        ANS+=i*(N//i*(N//i+1)//2)
    print(ANS)
main()
Buggy python submission (verdict: Time Limit Exceeded):
K=int(input())
S=input()
mod=10**9+7

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


LEN=len(S)
ANS=0
for i in range(K+1):
    ANS+=Combi(i+LEN-1,LEN-1)*pow(25,i,mod)*pow(26,K-i,mod)
print(ANS%mod)

Fixed submission:
K=int(input())
S=input()
mod=10**9+7

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


LEN=len(S)
ANS=0
for i in range(K+1):
    ANS+=Combi(i+LEN-1,LEN-1)*pow(25,i,mod)*pow(26,K-i,mod)
print(ANS%mod)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

S,K=input().split()
K=int(K)
mod=998244353

LEN=len(S)

ONES=[]
Z=0
for s in S:
    if s=="0":
        Z+=1
    else:
        ONES.append(Z)

O=len(ONES)
Z=ONES[-1]

DP=[[0]*(O+1) for i in range(O+1)]
DP[0][0]=1

# DP[i][j]で, i個石を動かし、j個石が残っているときの場合の数

from collections import Counter
C=Counter(ONES)

for numb in range(Z,-1,-1):
    #print(DP)
    c=C[numb]

    NDP=[[0]*(O+1) for i in range(O+1)]

    for i in range(O+1):        
        for j in range(O+1):
            if DP[i][j]==0:
                continue
            for oku in range(c+j+1):
                if i+max(0,oku-c)<=O and 0<=c+j-oku<=O:
                    NDP[i+max(0,oku-c)][c+j-oku]+=DP[i][j]
    DP=NDP

ANS=0
for i in range(min(O,K)+1):
    ANS+=DP[i][0]

print(ANS%mod)


Fixed submission:
import sys
input = sys.stdin.readline

S,K=input().split()
K=int(K)
mod=998244353

LEN=len(S)

ONES=[]
Z=0
for s in S:
    if s=="0":
        Z+=1
    else:
        ONES.append(Z)

if ONES==[]:
    print(1)
    sys.exit()

O=len(ONES)
Z=ONES[-1]

DP=[[0]*(O+1) for i in range(min(O,K)+1)]
DP[0][0]=1

# DP[i][j]で, i個石を動かし、j個石が残っているときの場合の数

from collections import Counter
C=Counter(ONES)

for numb in range(Z,-1,-1):
    #print(DP)
    c=C[numb]

    NDP=[[0]*(O+1) for i in range(min(O,K)+1)]

    for i in range(min(O,K)+1):        
        for j in range(O+1):
            if DP[i][j]==0:
                continue
            for oku in range(c+j+1):
                if i+max(0,oku-c)<=min(O,K) and 0<=c+j-oku<=O:
                    NDP[i+max(0,oku-c)][c+j-oku]+=DP[i][j]
    DP=NDP

ANS=0
for i in range(min(O,K)+1):
    ANS+=DP[i][0]

print(ANS%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,S=map(int,input().split())
A=list(map(int,input().split()))

mod=998244353

DP=[0]*(S+1)
DP[0]=pow(2,N,mod)

INV=pow(2,mod-2,mod)

for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]=(DP[i]*INV+DP[i+a])%mod
        
print(DP[S])


Fixed submission:
import sys
input = sys.stdin.readline

N,S=map(int,input().split())
A=list(map(int,input().split()))

mod=998244353

DP=[0]*(S+1)
DP[0]=pow(2,N,mod)

INV=pow(2,mod-2,mod)

for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]=(DP[i]*INV+DP[i+a])%mod
        
print(DP[S])

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

N,S=map(int,input().split())
A=list(map(int,input().split()))

mod=998244353

from collections import Counter
import copy

C=Counter()
C[(0,0)]=1

for a in A:
    C2=copy.deepcopy(C)
    for s,k in C:
        if s+a<=S:
            C2[(s+a,k+1)]+=C[(s,k)]
    C=C2
        
    
ANS=0
for s,k in C:
    if s==S:
        ANS=(ANS+pow(2,N-k,mod)*C[(s,k)])%mod
print(ANS)

Fixed submission:
import sys
input = sys.stdin.readline

N,S=map(int,input().split())
A=list(map(int,input().split()))

mod=998244353

DP=[0]*(S+1)
DP[0]=pow(2,N,mod)

INV=pow(2,mod-2,mod)

for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]=(DP[i]*INV+DP[i+a])%mod
        
print(DP[S])
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))

DOUB=[[-1]*(N+1) for i in range(62)]

DOUB[0]=[A[i] for i in range(N+1)]

for i in range(61):
    for j in range(N+1):
        DOUB[i+1][j]=DOUB[i][DOUB[i][j]]

NOW=1
while K:
    x=K.bit_length()-1
    NOW=DOUB[x][NOW]
    K-=1<<x
print(NOW)

Fixed submission:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))

DOUB=[[-1]*(N+1) for i in range(62)]

DOUB[0]=[A[i] for i in range(N+1)]

for i in range(61):
    for j in range(N+1):
        DOUB[i+1][j]=DOUB[i][DOUB[i][j]]

NOW=1
while K:
    x=K.bit_length()-1
    NOW=DOUB[x][NOW]
    K-=1<<x
print(NOW)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,M,S=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    E[u].append((v,a,b))
    E[v].append((u,a,b))

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<64]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print(min(DP[i]))

Fixed submission:
import sys
input = sys.stdin.readline

N,M,S=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    E[u].append((v,a,b))
    E[v].append((u,a,b))

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<60]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print(min(DP[i]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

A2=[(num,ind) for ind,num in enumerate(A)]
A2.sort(reverse=True)

L=[0]*N

for i in range(N):
    num,ind=A2[i]
    NL=[0]*N
    for j in range(i+1):
        right=N-1-(i-j)
        NL[j]=max(NL[j],abs(right-ind)*num+L[j])

        if j!=N-1:
            NL[j+1]=max(NL[j+1],abs(j-ind)*num+L[j])
        #print(i,j,right,num,ind,NL)
    L=NL
print(max(L))

Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

A2=[(num,ind) for ind,num in enumerate(A)]
A2.sort(reverse=True)

L=[0]*N

for i in range(N):
    num,ind=A2[i]
    NL=[0]*N
    for j in range(i+1):
        right=N-1-(i-j)
        NL[j]=max(NL[j],abs(right-ind)*num+L[j])

        if j!=N-1:
            NL[j+1]=max(NL[j+1],abs(j-ind)*num+L[j])
    L=NL
print(max(L))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,X,Y=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(1,N):
    E[i].append(i+1)
    E[i+1].append(i)
E[X].append(Y)
E[Y].append(X)

ANS=[0]*(N+1)
from collections import deque
for i in range(1,N+1):
    Q=deque()
    Q.append(i)
    D=[-1]*(N+1)
    D[i]=0
    
    while Q:
        x=Q.popleft()
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                ANS[D[to]]+=1
    #print(D)
for i in range(1,N):
    print(ANS[i]//2)
    


Fixed submission:
import sys
input = sys.stdin.readline

N,X,Y=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(1,N):
    E[i].append(i+1)
    E[i+1].append(i)
E[X].append(Y)
E[Y].append(X)

ANS=[0]*(N+1)
from collections import deque
for i in range(1,N+1):
    Q=deque()
    Q.append(i)
    D=[-1]*(N+1)
    D[i]=0
    
    while Q:
        x=Q.popleft()
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                ANS[D[to]]+=1
    #print(D)
for i in range(1,N):
    print(ANS[i]//2)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,list(input().strip())))

def next(A):
    B=[]
    for i in range(1,len(A)):
        B.append(abs(A[i]-A[i-1]))
    return B

A=next(A)
A=next(A)

if len(A)<=5:
    while len(A)>1:
        A=next(A)
    print(A[0])

else:
    if len(A)%2==1:
        A=next(A)

    if sum(A)%2==1:
        print(1)
    else:
        LEN=len(A)

        from collections import Counter
        C=Counter(A)

        if C[1]>0:
            print(0)
        elif C[0]==1 or C[2]==1:
            print(2)
        else:
            print(0)


Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,list(input().strip())))

def next(A):
    B=[]
    for i in range(1,len(A)):
        B.append(abs(A[i]-A[i-1]))
    return B

A=next(A)

if len(A)<=3:
    while len(A)>1:
        A=next(A)
    print(A[0])
    sys.exit()

def in2(x):
    if x==0:
        return 0
    ANS=0
    while x%2==0:
        ANS+=1
        x//=2
    return ANS


if not (1 in A):
    LEN=len(A)
    SUM=0
    COMBI=0

    for i in range(LEN):
        if COMBI==0:
            SUM+=A[i]//2

        COMBI=COMBI+in2(LEN-1-i)-in2(i+1)

    if SUM%2==1:
        print(2)
    else:
        print(0)
else:
    LEN=len(A)
    SUM=0
    COMBI=0

    for i in range(LEN):
        if COMBI==0:
            SUM+=A[i]

        COMBI=COMBI+in2(LEN-1-i)-in2(i+1)

    if SUM%2==1:
        print(1)
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N,mod=map(int,input().split())

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i][j]%=mod
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)

Fixed submission:
N,mod=map(int,input().split())

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i][j]%=mod
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)

Buggy python submission (verdict: Time Limit Exceeded):
N,mod=map(int,input().split())

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)

Fixed submission:
N,mod=map(int,input().split())

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i][j]%=mod
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)

Buggy python submission (verdict: Time Limit Exceeded):
N,mod=map(int,input().split())

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)

Fixed submission:
N,mod=map(int,input().split())

DP=[[0]*(N+5) for i in range(3*N+5)]
DP[0][0]=1

for i in range(3*N):
    for j in range(N+1):
        DP[i][j]%=mod
        DP[i+1][j]+=DP[i][j]
        DP[i+2][j+1]+=((3*N-i)-1)*DP[i][j]
        DP[i+3][j+1]+=((3*N-i)-1)*((3*N-i)-2)*DP[i][j]

ANS=0
for i in range(N+1):
    ANS+=DP[3*N][i]
print(ANS%mod)
Buggy python submission (verdict: Runtime Error):
for i in range(10**6):
    if i*8//100==A and i*10//100==B:
        print(i)
        break
else:
    print(-1)

Fixed submission:
A,B=map(int,input().split())

for i in range(10**6):
    if i*8//100==A and i*10//100==B:
        print(i)
        break
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N=int(input())
S=list(input().strip())
Q=int(input())

LEN=N

BIT=[[0]*(LEN+1) for i in range(26)]

def update(v,w,i): # index vにwを加える
    while v<=LEN:
        BIT[i][v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v,i): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[i][v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for i in range(N):
    update(i+1,1,ord(S[i])-97)

for i in range(Q):
    qf,x,y=input().split()
    qf=int(qf)

    if int(qf)==1:
        x=int(x)
        update(x,-1,ord(S[x-1])-97)
        update(x,1,ord(y)-97)
        S[x-1]=y

    else:
        x=int(x)
        y=int(y)
        ANS=0
        for i in range(26):
            if getvalue(y,i)-getvalue(x-1,i)>0:
                ANS+=1

        print(ANS)
        
    


Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
S=list(input().strip())
Q=int(input())

LEN=N

BIT=[[0]*(LEN+1) for i in range(26)]

def update(v,w,i): # index vにwを加える
    while v<=LEN:
        BIT[i][v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v,i): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[i][v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for i in range(N):
    update(i+1,1,ord(S[i])-97)

for i in range(Q):
    qf,x,y=input().split()
    qf=int(qf)

    if int(qf)==1:
        x=int(x)
        update(x,-1,ord(S[x-1])-97)
        update(x,1,ord(y)-97)
        S[x-1]=y

    else:
        x=int(x)
        y=int(y)
        ANS=0
        for i in range(26):
            if getvalue(y,i)-getvalue(x-1,i)>0:
                ANS+=1

        print(ANS)
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
r1,c1,r2,c2=map(int,input().split())

FACT=[1]
for i in range(1,2*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0

for x in range(c1+1,c2+2):
    ANS=(ANS+Combi(r2+x,r2)-Combi(r1+x-1,r1-1))%mod

print(ANS)


Fixed submission:
mod=10**9+7
r1,c1,r2,c2=map(int,input().split())

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0

for x in range(c1+1,c2+2):
    ANS=(ANS+Combi(r2+x,r2)-Combi(r1+x-1,r1-1))%mod

print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
H,N=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

D=[1<<31]*(H+10**4)
D[0]=0

for hp in range(H):
    for a,b in M:
        D[hp+a]=min(D[hp+a],D[hp]+b)
print(min(D[H:]))

Fixed submission:
H,N=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

D=[1<<31]*(H+10**4)
D[0]=0

for hp in range(H):
    for a,b in M:
        D[hp+a]=min(D[hp+a],D[hp]+b)
print(min(D[H:]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

DP=[0]*(N+1)
DP[0]=1

for k in range(K):
    use=A[k]

    NDP=[0]*(N+1)

    for i in range(N+1):
        ANS=0
        for j in range(N+1):
            ANS=(ANS+DP[j]*Combi(N-j,i-j)*Combi(N-(i-j),use-(i-j)))%mod

        NDP[i]=ANS

    DP=NDP

print(DP[N])

Fixed submission:
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

Combi=[[] for i in range(N+1)]
Combi[0]=[1,0]

for i in range(1,N+1):
    Combi[i].append(1)
    for j in range(i):
        Combi[i].append((Combi[i-1][j]+Combi[i-1][j+1])%mod)
    Combi[i].append(0)

DP=[0]*(N+1)
DP[0]=1

for k in range(K):
    use=A[k]

    NDP=[0]*(N+1)

    for i in range(N+1):
        ANS=0
        for j in range(i+1):
            if use-(i-j)>=0:
                ANS=(ANS+DP[j]*Combi[N-j][i-j]*Combi[N-(i-j)][use-(i-j)])%mod

        NDP[i]=ANS

    #print(DP)

    DP=NDP

print(DP[N])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import copy

N=int(input())
S=input().strip()

SUB={""}
ANS=set()

for s in S:
    NSUB=copy.deepcopy(SUB)
    for t in SUB:
        x=t+s
        if len(x)<=2:
            NSUB.add(x)
        else:
            ANS.add(x)

    SUB=NSUB

print(len(ANS))

Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
S=input().strip()

SUB={""}
ANS=set()

for s in S:
    N=set()
    for t in SUB:
        x=t+s
        if len(x)<=2:
            N.add(x)
        else:
            ANS.add(x)

    SUB|=N

print(len(ANS))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

mod=1000000007

DP=[0,0,0]
ANS=1

for a in A:
    ANS=ANS*DP.count(a)%mod
    x=DP.index(a)
    DP[x]+=1

print(ANS)


Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

mod=1000000007

DP=[0,0,0]
ANS=1

for a in A:
    ANS=ANS*DP.count(a)%mod
    if ANS==0:
        print(0)
        sys.exit()
    x=DP.index(a)
    DP[x]+=1

print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(N)]
D.sort()

DP=[0]*(T+1)
ANS=0

for i in range(N):
    a,b=D[i]

    for j in range(T,a-1,-1):
        DP[j]=max(DP[j-a]+b,DP[j])

    for j in range(i+1,N):
        ANS=max(ANS,DP[T-1]+D[j][1])

print(ANS)


Fixed submission:
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(N)]

D.sort(key=lambda x:x[1],reverse=True)

DP=[[0,0] for i in range(T+1)]

for ind,(x,y) in enumerate(D):
    for time in range(T,x-1,-1):
        if DP[time][0]<DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time]=[DP[time-x][0]+y,ind+1]
            else:
                DP[time]=[DP[time-x][0]+y,DP[time-x][1]]

        elif DP[time][0]==DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time][1]=min(ind+1,DP[time][1])
            else:
                DP[time][1]=min(DP[time-x][1],DP[time][1])

    #print(DP)

D.append((0,0))
                
ANS=DP[-1][0]

for x,y in DP[:-1]:
    #if x==0:
    #    continue
    ANS=max(ANS,x+D[y][1])

print(ANS)