Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
d={}
a=[]
for i in range(n):
  s=input()
  if s not in a:
    a.append(s)
  if s not in d:
    d[s]=1
  else:
    d[s]+=1
a.sort()
m=max(d.values())
for i in a:
  if d[i]==m:
    print(i)

Fixed submission:
n=int(input())
d={}
a=[]
for i in range(n):
  s=input()
  if s not in d:
    d[s]=1
    a.append(s)
  else:
    d[s]+=1
m=max(d.values())
a.sort()
for i in a:
  if d[i]==m:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=[input() for i in range(n)]
data=0
for i in s:
  data=max(s.count(i),data)
  
d=[]
for i in range(n):
  if s.count(s[i])==data and s[i] not in d:
    d.append(s[i])
d.sort()
for i in d:
  print(i)

Fixed submission:
n=int(input())
d={}
a=[]
for i in range(n):
  s=input()
  if s not in d:
    d[s]=1
    a.append(s)
  else:
    d[s]+=1
m=max(d.values())
a.sort()
for i in a:
  if d[i]==m:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = []
for _ in range(n):
  s = input()
  S.append(s)
S.sort()

l = max(S.count(i) for i in S)
ans = []
for j in S:
  if S.count(j) == l:
    if j not in ans:
      ans.append(j)
      print(j)

Fixed submission:
n=int(input())
d={}
a=[]
for i in range(n):
  s=input()
  if s not in d:
    d[s]=1
    a.append(s)
  else:
    d[s]+=1
m=max(d.values())
a.sort()
for i in a:
  if d[i]==m:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = []
for _ in range(n):
  s = input()
  S.append(s)
t = []
for i in S:
  l = S.count(i)
  t.append(l)
lm = max(t)
ans = []
for j in S:
  if S.count(j) == lm:
    if j not in ans:
      ans.append(j)
ans.sort()
for k in ans:
  print(k)

Fixed submission:
n=int(input())
d={}
a=[]
for i in range(n):
  s=input()
  if s not in d:
    d[s]=1
    a.append(s)
  else:
    d[s]+=1
m=max(d.values())
a.sort()
for i in a:
  if d[i]==m:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
res = 0
for i in a:
  if a.count(i) >= 2:
    res += 1
    
if res == 0:
  print('YES')
else:
  print('NO')


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

ans = set(a)
if len(ans) == n:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
  res=0
  for j in range(i,i+k):
    res+=p[j]/2+float(0.5)
  ans=max(ans,res)
print(ans)

Fixed submission:
n,k=map(int,input().split())
p=list(map(int,input().split()))
data=[0]*n
for i in range(n):
  data[i]=p[i]/2+float(0.5)
res=sum(data[0:k])
ans=sum(data[0:k])
for i in range(n-k):
  res-=data[i]-data[i+k]
  ans=max(ans,res)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
p=list(map(int,input().split()))
data=[0]*n
for i in range(n):
  data[i]=(p[i]/2)+float(0.5)
ans=0
for i in range(n-k+1):
  ans=max(ans,sum(data[i:i+k]))
print(ans)

Fixed submission:
n,k=map(int,input().split())
p=list(map(int,input().split()))
data=[0]*n
for i in range(n):
  data[i]=p[i]/2+float(0.5)
res=sum(data[0:k])
ans=sum(data[0:k])
for i in range(n-k):
  res-=data[i]-data[i+k]
  ans=max(ans,res)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))

data=[n+1]
for i in range(n):
  res=min(data)
  if res>p[i]:
    data.append(p[i])
print(len(data)-1)

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

ans = 0
for i in p:
  if i <= p[0]:
    p[0] = i
    ans += 1
print(ans)

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

ans = 0
for i in range(n):
  m = []
  for j in range(i+1):
    m.append(p[j])
  if min(m) == m[-1]:
    ans += 1
print(ans)

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

ans = 0
for i in p:
  if i <= p[0]:
    p[0] = i
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
ac=[0]*(n+1)
wa=0
for i in range(m+1):
  p,c=input().split()
  if c=='AC' and ac[int(p)]==0:
    ac[int(p)]=1
  elif c=='WA' and ac[int(p)]==0:
    wa+=1
print(ac.count(1),wa)

Fixed submission:
n, m = map(int, input().split())

ac = 0
wa = 0
res1 = [0]*n
res2 = [0]*n
for i in range(m):
  p, s = list(map(str, input().split()))
  if s == 'AC' and res1[int(p)-1] == 0:
    ac += 1
    res1[int(p)-1] = 1
    wa += res2[int(p)-1]
  elif s == 'WA' and res1[int(p)-1] == 0:
    res2[int(p)-1] += 1
print(ac, wa)
Buggy python submission (verdict: Runtime Error):
n=int(input())
m=rond(n/1.08)
if int(m*1.08)==n:
  print(m)
else:
  if int((m-1)*1.08)==n:
    print(m-1)
  elif int((m+1)*1.08)==n:
    print(m+1)
  else:
    print(':(')

Fixed submission:
n=int(input())
m=round(n/1.08)
if int(m*1.08)==n:
  print(m)
  exit()
else:
  if int((m-1)*1.08)==n:
    print(m-1)
    exit()
  elif int((m+1)*1.08)==n:
    print(m+1)
    exit()
  else:
    print(':(')
    exit()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
for i in range(n):
  d=abs(sum(a[0:i+1])-sum(a[i+1:n]))
  ans=min(ans,d)
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
s=sum(a)
res=0
for i in range(n):
  res+=a[i]
  s-=a[i]
  ans=min(ans,abs(s-res))
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
data=[0]
res=1
for i in range(1,len(s)):
  if s[i]==s[i-1] and data[i-1]==0:
    data.append(1)
  else:
    data.append(0)
if s[0]==s[-1] and data[-1]==0:
  res=2
  data.append(1)
  for i in range(1,len(s)):
    if s[i]==s[i-1] and data[i-1]==0:
      data.append(1)
    else:
      data.append(0)
if k%2==0:
  print(sum(data)*k//res)
else:
  if res==1:
    print(sum(data)*k)
  else:
    print(sum(data)*k//2+data[:len(s)])

Fixed submission:
s=input()
n=len(s)
k=int(input())
if s[0]==s[n-1]:
  d=1
  ans=0
  for i in range(1,n):
    if s[i-1]==s[i] and d==1:
      ans+=1
      d=0
    elif s[i-1]==s[i] and d==0:
      d=1
    elif s[i-1]!=s[i]:
      d=1
  if d==0:
    print(ans*k)
  else:
    ans2=0
    for i in range(n):
      if s[i-1]==s[i] and d==1:
        ans2+=1
        d=0
      elif s[i-1]==s[i] and d==0:
        d=1
      elif s[i-1]!=s[i]:
        d=1
    if d==1:
      print(ans+ans2*(k-1))
    else:
      if k%2==0:
        print((ans+ans2)*k//2)
      else:
        print((ans+ans2)*(k//2)+ans)
elif s[0]!=s[n-1]:
  d=1
  ans=0
  for i in range(1,n):
    if s[i-1]==s[i] and d==1:
      ans+=1
      d=0
    elif s[i-1]==s[i] and d==0:
      d=1
    elif s[i-1]!=s[i]:
      d=1
  print(ans*k)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  a.sort()
  a[-1]=a[-1]//2
print(sum(a))

Fixed submission:
import heapq
n,m=map(int,input().split())
a=list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(a)
for i in range(m):
  d=heapq.heappop(a)*(-1)
  heapq.heappush(a,(-1)*(d//2))
print(-sum(a))
Buggy python submission (verdict: Runtime Error):
n=int(input())
h=list(map(int,input().split()))

d=[0]*(n-1)
k=0
for i in range(n-1):
  if h[i]-h[i+1]>=0:
    d[k]+=1
  else:
    k+=1
print(max(d))

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

d=[0]*(n-1)
k=0
if n==1:
  print(0)
  exit()
for i in range(n-1):
  if h[i]-h[i+1]>=0:
    d[k]+=1
  else:
    k+=1
print(max(d))

Buggy python submission (verdict: Runtime Error):
n=int(input())
h=list(map(int,input().split()))

d=[0]*(n-1)
k=0
for i in range(n-1):
  if h[i]-h[i+1]>=0:
    d[k]+=1
  else:
    k+=1
print(max(d))

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

d=[0]*(n-1)
k=0
if n==1:
  print(0)
  exit()
for i in range(n-1):
  if h[i]-h[i+1]>=0:
    d[k]+=1
  else:
    k+=1
print(max(d))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = []
for _ in range(n):
  a_ = int(input())
  a.append(a_)
  
for i in range(n):
  res = a[i]
  a[i] = 0
  print(max(a))
  a[i] = res


Fixed submission:
n = int(input())
a = []
for _ in range(n):
  a_ = int(input())
  a.append(a_)
a1 = sorted(a)
ans1 = a1[-1]
ans2 = a1[-2]
for i in range(n):
  if a[i] == ans1:
    print(ans2)
  else:
    print(ans1)
Buggy python submission (verdict: Time Limit Exceeded):
L,R=map(int,input().split())
l=L%2019
r=R%2019
l1=L//2019
r1=R//2019
if l1<r1:
  print(0)
elif l1==r1:
  res=[]
  for i in range(l,r):
    for j in range(i+1,r+1):
      if (i*j)%2019 not in res:
        res.append((i*j)%2019)
  print(min(res))

Fixed submission:
l, r = map(int, input().split())

if l + 2019 <= r:
  print(0)
else:
  res = []
  for i in range(l, r+1):
     for j in range(i+1, r+1):
        res.append((i*j)%2019)
  print(min(res))

Buggy python submission (verdict: Runtime Error):
L,R=map(int,input().split())
l=L%2019
r=R%2019
l1=L//2019
r1=R//2019
if l1<r1:
  print(0)
elif l1==r1:
  res=[]
  for i in range(l,r):
    for j in range(i+1,r+1):
      if (i*j)%2019 not in res:
        res.append((i*j)%2019)
print(min(res))

Fixed submission:
l, r = map(int, input().split())

if l + 2019 <= r:
  print(0)
else:
  res = []
  for i in range(l, r+1):
     for j in range(i+1, r+1):
        res.append((i*j)%2019)
  print(min(res))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
d=[0]*(n+1)
d[0]=1
d[1]=1
if 1 in a:
  d[1]=0
for i in range(2,n+1):
  if i in a:
    d[i]=0
  else:
    d[i]=d[i-1]+d[i-2]
print(d[n]%(10**9+7))

Fixed submission:
n, m = map(int, input().split())
a = set()
for _ in range(m):
  a_ = int(input())
  a.add(a_)

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

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

d = [1] + [1]*n
for i in range(1, n):
  if i in a:
    d[i] = 0
    d[i+1] = d[i-1]
  else:
    d[i+1] = d[i] + d[i-1]
    
print(d[n]%1000000007)

Fixed submission:
n, m = map(int, input().split())
a = set()
for _ in range(m):
  a_ = int(input())
  a.add(a_)

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = []
for _ in range(m):
  a_ = int(input())
  a.append(a_)

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

Fixed submission:
n, m = map(int, input().split())
a = set()
for _ in range(m):
  a_ = int(input())
  a.add(a_)

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
n , m = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(m)]

d = [0]*n
for i in range(m):
  for j in range(lr[i][0]-1, lr[i][1]):
    d[j] += 1
    
print(d.count(m))

Fixed submission:
n, m = map(int, input().split())

a=0
b=n
for i in range(m):
  l, r = map(int, input().split())
  a = max(a, l)
  b = min(b, r)
if b-a+1 >= 0:
  print(b-a+1)
else:
  print(0)

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

a=[0]*n
for i in range(m):
  l, r = map(int, input().split())
  for j in range(l,r+1):
    a[j-1] += 1
print(a.count(m))

Fixed submission:
n, m = map(int, input().split())

a=0
b=n
for i in range(m):
  l, r = map(int, input().split())
  a = max(a, l)
  b = min(b, r)
if b-a+1 >= 0:
  print(b-a+1)
else:
  print(0)

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

a = [0]*n
for i in range(m):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    a[j-1] += 1

print(a.count(m))

Fixed submission:
n, m = map(int, input().split())

a=0
b=n
for i in range(m):
  l, r = map(int, input().split())
  a = max(a, l)
  b = min(b, r)
if b-a+1 >= 0:
  print(b-a+1)
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
s = list(input())

a = int(s[0]+s[1])
b = int(s[2]+s[3])

if  1<=a<=12 and 1<=b<=12:
  print('AMBIGUOUS')
elif a>12 and 1<=b<=12:
  print('YYMM')
elif b>12 and 1<=a<=12:
  print('MMYY')
elif a>12 and b>12:
  print('NA')
elof a<0 and b<0:
  print('NA')

Fixed submission:
s = list(input())

a = int(s[0]+s[1])
b = int(s[2]+s[3])

if  1<=a<=12 and 1<=b<=12:
  print('AMBIGUOUS')
elif (a>12 or a==0) and 1<=b<=12:
  print('YYMM')
elif (b>12 or b==0) and 1<=a<=12:
  print('MMYY')
elif (a>12 or a==0) and (b>12 or b==0):
  print('NA')
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,n=map(int,input().split())
r=n//R
g=n//G
b=n//B
ans=0
if max(r,g,b)==b:
  for i in range(r+1):
    for j in range(g+1):
      if (n-R*i-G*j)%B==0 and n-R*i-G*j>=0:
        ans+=1
elif max(r,g,b)==g:
  for i in range(r+1):
    for j in range(b+1):
      if (n-R*i-B*j)%G==0 and n-R*i-B*j>=0:
        ans+=1
elif max(r,g,b)==r:
  for i in range(b+1):
    for j in range(g+1):
      if (n-B*i-G*j)%R==0 and n-B*i-G*j>=0:
        ans+=1
print(ans)

Fixed submission:
R,G,B,n=map(int,input().split())
r=n//R
g=n//G
b=n//B
ans=0
for i in range(r+1):
  for j in range((n-R*i)//G+1):
    if (n-i*R-j*G)%B==0:
      ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,n=map(int,input().split())
r=n//R
g=n//G
ans=0
for i in range(r+1):
  for j in range(g+1):
    if (n-R*i-G*j)%B==0 and n-R*i-G*j>=0:
      ans+=1
print(ans)

Fixed submission:
R,G,B,n=map(int,input().split())
r=n//R
g=n//G
b=n//B
ans=0
for i in range(r+1):
  for j in range((n-R*i)//G+1):
    if (n-i*R-j*G)%B==0:
      ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,n=map(int,input().split())
r=n//R
g=n//G
b=n//B
ans=0
for i in range(r+1):
  for j in range(g+1):
    if (n-R*i-G*j)%B==0 and n-R*i-G*j>=0:
      ans+=1
print(ans)

Fixed submission:
R,G,B,n=map(int,input().split())
r=n//R
g=n//G
b=n//B
ans=0
for i in range(r+1):
  for j in range((n-R*i)//G+1):
    if (n-i*R-j*G)%B==0:
      ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
  r,l=map(int,input().split())
  ans=0
  for j in range(r-1,l-1):
    if s[j]=='A' and s[j+1]=='C':
      ans+=1
  print(ans)

Fixed submission:
n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
data=[0]*(n+1)
if s[0]=='A' and s[1]=='C':
  data[1]=1
for i in range(1,n-1):
  if s[i]=='A' and s[i+1]=='C':
    data[i+1]+=1
  data[i+1]+=data[i]
data[n]=data[n-1]
for i in range(q):
  print(data[lr[i][1]-1]-data[lr[i][0]-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
  l,r=map(int,input().split())
  print(s[l-1:r].count('AC'))

Fixed submission:
n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
data=[0]*(n+1)
if s[0]=='A' and s[1]=='C':
  data[1]=1
for i in range(1,n-1):
  if s[i]=='A' and s[i+1]=='C':
    data[i+1]+=1
  data[i+1]+=data[i]
data[n]=data[n-1]
for i in range(q):
  print(data[lr[i][1]-1]-data[lr[i][0]-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
for i in range(q):
  l, r = map(int, input().split())
  ans = 0
  for i in range(l-1, r-1):
    if s[i]=='A' and s[i+1]=='C':
      ans += 1
  
  print(ans)

Fixed submission:
n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
data=[0]*(n+1)
if s[0]=='A' and s[1]=='C':
  data[1]=1
for i in range(1,n-1):
  if s[i]=='A' and s[i+1]=='C':
    data[i+1]+=1
  data[i+1]+=data[i]
data[n]=data[n-1]
for i in range(q):
  print(data[lr[i][1]-1]-data[lr[i][0]-1])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
data=[0]*n
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,a[0]+1):
    data[a[j]-1]+=1
print(data.count(n))

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

dp = [float('inf')] * n

dp[0] = 0
for i in range(n):
  for j in range(i+1):
    if j <= k:
      dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
    
    
print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * n

dp[0] = 0
for i in range(1, n):
  dp[i] = min(dp[j]+abs(h[i]-h[j]) for j in range(max(0, i-k), i))

    
print(dp[n-1])

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

dp = [float('inf')] * n

dp[0] = 0
for i in range(n):
  for j in range(k+1):
    if i-j>=0:
      dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))
    
    
print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * n

dp[0] = 0
for i in range(1, n):
  dp[i] = min(dp[j]+abs(h[i]-h[j]) for j in range(max(0, i-k), i))

    
print(dp[n-1])

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * n

dp[0] = 0
for i in range(n):
  for j in range(k+1):
    dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))
    
    
print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * n

dp[0] = 0
for i in range(1, n):
  dp[i] = min(dp[j]+abs(h[i]-h[j]) for j in range(max(0, i-k), i))

    
print(dp[n-1])

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

dp = [float('inf')] * n

dp[0] = 0
for i in range(1, n):
  if i == 1:
    dp[i] = abs(h[i]-h[i-1])
  else:
    res = float('inf')
    for j in range(1, k+1):
      if i-j>=0:
        res = min(dp[i-j] + abs(h[i]-h[i-j]), res)
    dp[i] = res
    
print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')] * n

dp[0] = 0
for i in range(1, n):
  dp[i] = min(dp[j]+abs(h[i]-h[j]) for j in range(max(0, i-k), i))

    
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
  
dp = [0] * (W+1)

for i in range(n):
  for j in range(W, w[i]-1, -1):
    dp[j] = max(dp[j], dp[j-w[i]]+v[i])
    
print(dp[W])

Fixed submission:
import numpy as np

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
  dp[w[i]:] = np.maximum(dp[:-w[i]]+v[i], dp[w[i]:])
print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
  
dp = [[0]*(W+1) for i in range(N+1)]


for i in range(N):
  for j in range(W+1):
    if j >= w[i]:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
    else:
      dp[i+1][j] = dp[i][j]
print(dp[N][W])

Fixed submission:
import numpy as np

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
  dp[w[i]:] = np.maximum(dp[:-w[i]]+v[i], dp[w[i]:])
print(dp[W])
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
n=len(S)
m=len(T)
dp=[['']*(m+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if S[i-1]==T[j-1]:
      dp[i][j]=dp[i-1][j-1]+S[i-1]
    else:
      if len(dp[i][j-1])>=len(dp[i-1][j]):
        dp[i][j]=dp[i][j-1]
      else:
        dp[i][j]=dp[i-1][j]
print(dp[n][m])

Fixed submission:
S=input()
T=input()
n=len(S)
m=len(T)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j]+(S[i]==T[j]))
ans=''
while n>0 and m>0:
  if dp[n][m]==dp[n-1][m]:
    n-=1
  elif dp[n][m]==dp[n][m-1]:
    m-=1
  else:
    n-=1
    m-=1
    ans=S[n]+ans
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
n=len(S)
m=len(T)
dp=[['']*(m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    if S[i]==T[j]:
      dp[i+1][j+1]=dp[i][j]+S[i]
    else:
      if len(dp[i+1][j])>=len(dp[i][j+1]):
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
print(dp[n][m])

Fixed submission:
S=input()
T=input()
n=len(S)
m=len(T)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j]+(S[i]==T[j]))
ans=''
while n>0 and m>0:
  if dp[n][m]==dp[n-1][m]:
    n-=1
  elif dp[n][m]==dp[n][m-1]:
    m-=1
  else:
    n-=1
    m-=1
    ans=S[n]+ans
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n,m=map(int,input().split())
d=defaultdict(list)
for _ in range(m):
  x,y=map(int,input().split())
  d[x-1].append(y-1)

dp=[-1]*n

def rec(v):
  if dp[v]!=-1:
    return dp[v]
  res=0
  for nv in d[v]:
    res=max(res,rec(nv)+1)
  dp[v]=res
  return res

res=0
for v in range(n):
  res=max(res,rec(v))
print(res)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(list)
for _ in range(m):
  x,y=map(int,input().split())
  d[x-1].append(y-1)

dp=[-1]*n

def rec(v):
  if dp[v]!=-1:
    return dp[v]
  res=0
  for nv in d[v]:
    res=max(res,rec(nv)+1)
  dp[v]=res
  return res

res=0
for v in range(n):
  res=max(res,rec(v))
print(res)
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter

n, m = map(int, input().split())
yp = []
for i in range(m):
  p_, y_ = map(int, input().split())
  yp.append([y_, p_, i+1])
py = sorted(yp)
ken = [0]*m
res = []
for i in range(m):
  ken[py[i][1]] += 1
  p, q, r = py[i][1], ken[py[i][1]], py[i][2]
  res.append([p, q, r])
#print(yp)
#print(py)

res.sort(key=itemgetter(2))
#print(res)
for i in range(m):
  ans1 = [0]*(6-len(str(res[i][0])))
  ans1.append(res[i][0])
  ans2 = [0]*(6-len(str(res[i][1])))
  ans2.append(res[i][1])
  print(*ans1, *ans2, sep='')

Fixed submission:
from operator import itemgetter

n, m = map(int, input().split())
yp = []
for i in range(m):
  p_, y_ = map(int, input().split())
  yp.append([y_, p_, i+1])
py = sorted(yp)
ken = [0]*n
res = []
for i in range(m):
  ken[py[i][1]-1] += 1
  p, q, r = py[i][1], ken[py[i][1]-1], py[i][2]
  res.append([p, q, r])
#print(yp)
#print(py)

res.sort(key=itemgetter(2))
#print(res)
for i in range(m):
  ans1 = [0]*(6-len(str(res[i][0])))
  ans1.append(res[i][0])
  ans2 = [0]*(6-len(str(res[i][1])))
  ans2.append(res[i][1])
  print(*ans1, *ans2, sep='')
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
res=n*m//gcd(n,m)
for i in range(res):
  if i*n/res==int(i*n/res) and i*m/res==int(i*m/res):
    if s[i*n//res]!=t[i*m//res]:
      print('-1')
      exit()
print(res)

Fixed submission:
from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
res=n*m//gcd(n,m)
a=m//gcd(n,m)
b=n//gcd(n,m)
if n>=m:
  for i in range(m):
    if (i*b)%a==0:
      if s[(i*b)//a]!=t[i]:
        print(-1)
        exit()
else:
  for i in range(n):
    if (i*a)%b==0:
      if s[i]!=t[(i*a)//b]:
        print(-1)
        exit()
print(res)