Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=[[0]*n for _ in range(100)]
A=list(map(int,input().split()))
for i,j in enumerate(A):
    a[0][i]=j-1
i=1
while 2**i<k:
    for x,y in enumerate(a[i-1]):
        a[i][x]=a[i-1][y]
    i+=1
x=0
for j in range(i):
    if k>>j&1:
        x=a[j][x]
print(x+1)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
chk=[False]*n
x=0
visit=[0]
chk[x]=True
while chk:
    x=a[x]-1
    if chk[x]:
        break
    else:
        visit.append(x)
        chk[x]=True
l1=0
while visit[l1]!=x:
    l1+=1
l2=len(visit)-l1
if k>=l1:
    print(visit[l1+((k-l1)%l2)]+1)
else:
    print(visit[k]+1)
Buggy python submission (verdict: Runtime Error):
    x=int(input())
    for a in range(-118,120):
        for b in range(-118,120):
            if a**5-b**5==x:
                print(a,b)
                exit()

Fixed submission:
x=int(input())
for a in range(-118,120):
    for b in range(-118,120):
        if a**5-b**5==x:
            print(a,b)
            exit()
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(list(map(int,input().split())))
ma=max(a)
l,r=[0]*(ma+n+1),[0]*(ma+n+1)
for i,a in enumerate(a):
    l[i+a]+=1
    if i-a<0:
        continue
    else:
        r[i-a]+=1
ans=0
for a,b in zip(l,r):
    ans+=a*b
print(ans)

Fixed submission:
from collections import Counter
n=int(input())
a=list(list(map(int,input().split())))
ma=[i-a[i] for i in range(n)]
r=Counter(ma)
ans=0
for i in range(n):
    ans+=r[i+a[i]]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(list(map(int,input().split())))
for i in range(n):
    a[i]-=i
ans=0
for i in range(n-1):
    h=-(a[i]+2*i)
    ans+=a[i+1:].count(h)
print(ans)

Fixed submission:
from collections import Counter
n=int(input())
a=list(list(map(int,input().split())))
ma=[i-a[i] for i in range(n)]
r=Counter(ma)
ans=0
for i in range(n):
    ans+=r[i+a[i]]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(list(map(int,input().split())))
ans=0
for i in range(n):
    h=a[i]
    if i+h>n-1:
        continue
    else:
        for j in range(i+h,n):
            if j-i==h+a[j]:
                ans+=1
print(ans)

Fixed submission:
from collections import Counter
n=int(input())
a=list(list(map(int,input().split())))
ma=[i-a[i] for i in range(n)]
r=Counter(ma)
ans=0
for i in range(n):
    ans+=r[i+a[i]]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(list(map(int,input().split())))
ans=0
for i in range(n):
    h=a[i]
    if i+h>n-1:
        continue
    else:
        for j in range(i+h,n):
            if j-i==h+a[j]:
                ans+=1
print(ans)

Fixed submission:
from collections import Counter
n=int(input())
a=list(list(map(int,input().split())))
ma=[i-a[i] for i in range(n)]
r=Counter(ma)
ans=0
for i in range(n):
    ans+=r[i+a[i]]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(list(map(int,input().split())))
ans=0
for i in range(n):
    if i+a[i]>n-1:
        continue
    else:
        for j in range(i+a[i],n):
            if j-i==a[i]+a[j]:
                ans+=1
print(ans)

Fixed submission:
from collections import Counter
n=int(input())
a=list(list(map(int,input().split())))
ma=[i-a[i] for i in range(n)]
r=Counter(ma)
ans=0
for i in range(n):
    ans+=r[i+a[i]]
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
N=2*m+1
if m%2==0:
    for i in range(m//2):
        print(i+1,m+1-i)
        print(m+2+i,N-i)
else:
    for i in range(m//2):
        print(i+1,m-i)
        print(m+1+i,N-i)
    print(m+1+i+1,N-i-1)

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

for i in range(M):
    j = i // 2
    if i % 2 == 1:
        print(j+1, M-j)
    else:
        print(M+j+1, 2*M+1-j)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
N=2*m+1
if m%2==0:
    for i in range(m//2):
        print(i+1,m+1-i)
        print(m+2+i,N-i)
else:
    for i in range(m//2):
        print(i+1,m-i)
        print(m+1+i,N-i)
    print(m+1+i+1,N-i-1)

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

for i in range(M):
    j = i // 2
    if i % 2 == 1:
        print(j+1, M-j)
    else:
        print(M+j+1, 2*M+1-j)
Buggy python submission (verdict: Runtime Error):
s=list(map(int,list(input())))
n=len(s)
m=[[0]*(n+1) for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    for j in range(i,n+1):
        m[i][j]=(m[i][j-1]*10+s[j-1])%2019
        if m[i][j]==0:
            ans+=1
print(ans)

Fixed submission:
s,w=map(int,input().split())
if w>=s:
    print('unsafe')
else:
    print('safe')
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
sl=list(map(int,list(s)))
n=len(s)
sums=[0]*(n+1)
ans=0
for i in range(1,n+1):
    sums[i]=sums[i-1]+sl[i-1]
for i in range(n-4):
    for j in range(i+4,n):
        if (sums[j+1]-sums[i])%3==0:
            if int(s[i:j+1])%2019==0:
                ans+=1
print(ans)

Fixed submission:
s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
sl=list(map(int,list(s)))
n=len(s)
ans=0
for i in range(n-4):
    for j in range(i+4,n):
        if sum(sl[i:j+1])%3==0:
            if int(s[i:j+1])%2019==0:
                ans+=1
print(ans)

Fixed submission:
s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=list(map(int,list(input())))
n=len(s)
m=[[0]*(n+1) for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    for j in range(i,n+1):
        m[i][j]=(m[i][j-1]*10+s[j-1])%2019
        if m[i][j]==0:
            ans+=1
print(ans)

Fixed submission:
s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=list(map(int,list(input())))
n=len(s)
m=[[0]*(n+1) for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    for j in range(i,n+1):
        m[i][j]=(m[i][j-1]*10+s[j-1])%2019
        if m[i][j]==0:
            ans+=1
print(ans)

Fixed submission:
s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
l=[[] for _ in range(ma+1)]
chk=[0]*n
ans=0
for i,x in enumerate(a):
    l[x].append(i)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(ma,0,-1):
    for j in l[i]:
        for x in range(cnt+1):
            if x==0:
                dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
            elif x==cnt:
                dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
            else:
                dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
        cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
l=[]
for i,x in enumerate(a):
    l.append([x,i])
l.sort(reverse=True)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i,j in l:
    for x in range(cnt+1):
        if x==0:
            dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
        elif x==cnt:
            dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
        else:
            dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
    cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
l=[[] for _ in range(ma+1)]
chk=[0]*n
ans=0
for i,x in enumerate(a):
    l[x].append(i)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(ma,0,-1):
    for j in l[i]:
        for x in range(cnt+1):
            if x==0:
                dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
            elif x==cnt:
                dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
            else:
                dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
        cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
l=[]
for i,x in enumerate(a):
    l.append([x,i])
l.sort(reverse=True)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i,j in l:
    for x in range(cnt+1):
        if x==0:
            dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
        elif x==cnt:
            dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
        else:
            dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
    cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][sw]-cnt[g[i]][sw-1]-cnt[g[i-1]][sw]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+2
                    j=w
                    break            
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()


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

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][sw]-cnt[g[i]][sw-1]-cnt[g[i-1]][sw]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+2
                    j=w
                    break            
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def main():
    def calc(n, mod):
        f = 1
        for m in range(1, n + 1):
            f *= m
            f %= mod
        fn = f
        inv = pow(f, mod - 2, mod)
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= mod
            invs[m - 1] = inv 
        return fn, invs

    mod = 10**9+7
    n,a,b=map(int,input().split())
    ans=0
    fn,invs=calc(n,mod)
    for i in range(1,n+1):
        if i==a or i==b:
            continue
        else:
            ans+=(invs[i]*invs[n-i])%mod
    print((fn*ans)%mod)

if __name__ == '__main__':
    main()

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

def main():
    n,r=map(int,input().split())
    if n>=10:
        print(r)
    else:
        print(int(100*(10-n)+r))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    def calc(n, mod):
        f = 1
        for m in range(1, n + 1):
            f *= m
            f %= mod
        fn = f
        inv = pow(f, mod - 2, mod)
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= mod
            invs[m - 1] = inv 
        return fn, invs

    mod = 10**9+7
    n,a,b=map(int,input().split())
    ans=0
    fn,invs=calc(n,mod)
    for i in range(1,n+1):
        if i==a or i==b:
            continue
        else:
            ans+=(invs[i]*invs[n-i])%mod
    print((fn*ans)%mod)

if __name__ == '__main__':
    main()

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

def main():
    mod = 10**9+7
    n,a,b=map(int,input().split())
    f=1
    fa=0
    for i in range(1,b+1):
        f=(f*(n-i+1)*pow(i,mod-2,mod))%mod
        if i==a:
            fa=f
    ans=(pow(2,n,mod)-fa-f-1)%mod
    print(ans)

if __name__ == '__main__':
    main()

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

def main():
    def calc(n, mod):
        f = 1
        for m in range(1, n + 1):
            f *= m
            f %= mod
        fn = f
        inv = pow(f, mod - 2, mod)
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= mod
            invs[m - 1] = inv 
        return fn, invs

    mod = 10**9+7 
    n,a,b=map(int,input().split())
    ans=0
    fn,invs=calc(n,mod)
    for i in range(1,n+1):
        if i==a or i==b:
            continue
        else:
            ans+=(fn*invs[i]*invs[n-i])%mod
    print(ans)

if __name__ == '__main__':
    main()

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

def main():
    mod = 10**9+7
    n,a,b=map(int,input().split())
    f=1
    fa=0
    for i in range(1,b+1):
        f=(f*(n-i+1)*pow(i,mod-2,mod))%mod
        if i==a:
            fa=f
    ans=(pow(2,n,mod)-fa-f-1)%mod
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N, K = map(int,input().split())
    A = np.sort(np.array(list(map(int, input().split())), np.int64))
    z = A[A == 0]
    p = A[A > 0]
    n = A[A < 0]
    
    def count_func(x):
        cnt = 0
        if x >= 0:
            cnt += len(z) * N
        cnt += np.searchsorted(A, x // p, side='right').sum()
        cnt += (N - np.searchsorted(A, -(-x // n), side='left')).sum()
        cnt -= np.count_nonzero(A * A <= x)
        assert cnt % 2 == 0
        return cnt // 2
    
    l = -10 ** 18
    r = 10 ** 18
    while l + 1 < r:
        x = (l + r) // 2
        if count_func(x) >= K:
            r = x
        else:
            l = x
    
    print(r)
    
if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N, K = map(int,input().split())
    A = np.sort(np.array(list(map(int, input().split())), np.int64))
    z = A[A == 0]
    p = A[A > 0]
    n = A[A < 0]
    
    def count_func(x):
        cnt = 0
        if x >= 0:
            cnt += len(z) * N
        cnt += np.searchsorted(A, x // p, side='right').sum()
        cnt += (N - np.searchsorted(A, -(-x // n), side='left')).sum()
        cnt -= np.count_nonzero(A * A <= x)
        assert cnt % 2 == 0
        return cnt // 2
    
    l = -10 ** 18
    r = 10 ** 18
    while l + 1 < r:
        x = (l + r) // 2
        if count_func(x) >= K:
            r = x
        else:
            l = x
    
    print(r)
    
if __name__ == '__main__':
    main()

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

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    ans=[0]*(int(n*(n-1)/2))
    cnt=0
    for i in range(n):
        for j in range(i,n):
            if i==j:
                continue
            else:
                ans[cnt]=a[i]*a[j]
            cnt+=1
    ans.sort()
    print(ans[k-1])
    
if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N, K = map(int,input().split())
    A = np.sort(np.array(list(map(int, input().split())), np.int64))
    z = A[A == 0]
    p = A[A > 0]
    n = A[A < 0]
    
    def count_func(x):
        cnt = 0
        if x >= 0:
            cnt += len(z) * N
        cnt += np.searchsorted(A, x // p, side='right').sum()
        cnt += (N - np.searchsorted(A, -(-x // n), side='left')).sum()
        cnt -= np.count_nonzero(A * A <= x)
        assert cnt % 2 == 0
        return cnt // 2
    
    l = -10 ** 18
    r = 10 ** 18
    while l + 1 < r:
        x = (l + r) // 2
        if count_func(x) >= K:
            r = x
        else:
            l = x
    
    print(r)
    
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from math import factorial

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

n=int(input())
k=int(input())
ans=0
nstr=str(n)
nl=len(nstr)
for i in range(k,nl):
    ans+=combinations_count(i-1,k-1)
ans*=9**k
zerocnt=0
for i in range(nl):
    if zerocnt<=nl-k:
        if i==0:
            ans+=(int(nstr[0])-1)*combinations_count(nl-1,k-1)*(9**(k-1))
        else:
            if nstr[i]=='0':
                zerocnt+=1
            else:
                ans+=(int(nstr[i])-1)*combinations_count(nl-i-1,k-i+zerocnt-1)*9**(k-i+zerocnt-1)
    else:
        break
print(ans)

Fixed submission:
s=input()
K=int(input())
n=len(s)
dp=[[[0]*2 for _ in range(K+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(n):
    for j in range(K+1):
        for k in range(2):
            nd=int(s[i])
            for d in range(10):
                ni,nj,nk=i+1,j,k
                if d!=0:
                    nj+=1
                if nj>K:
                    continue
                if nk==0:
                    if nd<d:
                        continue
                    if nd>d:
                        nk=1
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[n][K][0]+dp[n][K][1])
Buggy python submission (verdict: Runtime Error):
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp =[0]*(h+max(ab[0:n][0]))
    for i in range(1, h+1):
        dp[i] = min(dp[i-a]+b for a,b in ab)
    print(dp[h])
      
if __name__ == '__main__':
    main()

Fixed submission:
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp =[0]*(h+max(a for a,b in ab))
    for i in range(1, h+1):
        dp[i] = min(dp[i-a]+b for a,b in ab)
    print(dp[h])
      
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp =[0]*(h+max(ab[0:n][0]))
for i in range(1, h+1):
  dp[i] = min(dp[i-a]+b for a,b in ab)
print(dp[h])

Fixed submission:
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp =[0]*(h+max(a for a,b in ab))
    for i in range(1, h+1):
        dp[i] = min(dp[i-a]+b for a,b in ab)
    print(dp[h])
      
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())
2.ab = [list(map(int, input().split())) for _ in range(n)]
3.dp =[0]*(h+max(ab[0:n][0]))
4.for i in range(1, h+1):
5.  dp[i] = min(dp[i-a]+b for a,b in ab)
6.print(dp[h])

Fixed submission:
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp =[0]*(h+max(a for a,b in ab))
    for i in range(1, h+1):
        dp[i] = min(dp[i-a]+b for a,b in ab)
    print(dp[h])
      
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp =[0]*(h+max(ab[0:n][1]))
for i in range(1, h+1):
  dp[i] = min(dp[i-a]+b for a,b in ab)
print(dp[h])

Fixed submission:
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp =[0]*(h+max(a for a,b in ab))
    for i in range(1, h+1):
        dp[i] = min(dp[i-a]+b for a,b in ab)
    print(dp[h])
      
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
x,l,dcnt=[0]*n,[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
for i in range(n-1):
  chk=xlr[i][1]
  cnt=0
  for j in range(i+1,n):
    if xlr[j][0]<chk:
      cnt+=1
    else:
      break
  dcnt[i]=cnt
cnt=0
for i in range(1,n+1):
  if dcnt[n-i]>0:
    dcnt[n-i]=0
    cnt+=1
    for j in range(n-i):
      if dcnt[n-i-j-1]>j:
        dcnt[n-i-j-1]-=1
print(n-cnt)

Fixed submission:
h=int(input())
w=int(input())
n=int(input())
flg,cnt,pn=0,0,0
mh,mw=h,w
hcnt,wcnt=h,w
while pn<n:
  if mh==mw:
    if hcnt>wcnt:
      flg=0
    else:
      flg=1
  elif mh>mw:
    flg=1
  else:
    flg=0
  if flg==1:
    pn+=mh
    wcnt-=1
    mw-=1
    cnt+=1
  else:
    pn+=mw
    hcnt-=1
    mh-=1
    cnt+=1    
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
x,l,dcnt=[0]*n,[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
for i in range(n-1):
  chk=xlr[i][1]
  cnt=0
  for j in range(i+1,n):
    if xlr[j][0]<chk:
      cnt+=1
    else:
      break
  dcnt[i]=cnt
cnt=0
for i in range(1,n+1):
  if dcnt[n-i]>0:
    dcnt[n-i]=0
    cnt+=1
    for j in range(n-i):
      if dcnt[n-i-j-1]>j:
        dcnt[n-i-j-1]-=1
print(n-cnt)

Fixed submission:
n=int(input())
x,l=[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
cnt=0
chk=xlr[n-1][0]
for i in range(2,n+1):
  if chk<xlr[n-i][1]:
    cnt+=1
  else:
    chk=xlr[n-i][0]
print(n-cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
x,l,dcnt=[0]*n,[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
for i in range(n-1):
  chk=xlr[i][1]
  cnt=0
  for j in range(i+1,n):
    if xlr[j][0]<chk:
      cnt+=1
    else:
      break
  dcnt[i]=cnt
cnt=0
for i in range(1,n+1):
  if dcnt[n-i]>0:
    dcnt[n-i]=0
    cnt+=1
    for j in range(n-i):
      if dcnt[n-i-j-1]>j:
        dcnt[n-i-j-1]-=1
print(n-cnt)

Fixed submission:
n=int(input())
x,l=[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
cnt=0
chk=xlr[n-1][0]
for i in range(2,n+1):
  if chk<xlr[n-i][1]:
    cnt+=1
  else:
    chk=xlr[n-i][0]
print(n-cnt)