Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
for i in range(n):
    nb = np.copy(na)
    nb[i] = 0
    print(np.max(nb))

Fixed submission:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
maxI = np.argmax(na)
maxA = na[maxI]
nb = np.copy(na)
nb[maxI] = 0
maxA2 = np.max(nb)
for i in range(n):
    if i != maxI:
        print(na[maxI])
    else:
       print(maxA2)

Buggy python submission (verdict: Runtime Error):
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
for i in range(n):
    nb = np.copy(na)
    nb[i] = 0
    print(np.max(nb))

Fixed submission:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
maxI = np.argmax(na)
maxA = na[maxI]
nb = np.copy(na)
nb[maxI] = 0
maxA2 = np.max(nb)
for i in range(n):
    if i != maxI:
        print(na[maxI])
    else:
       print(maxA2)

Buggy python submission (verdict: Runtime Error):
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
for i in range(n):
    print(np.max(a[:i] + a[i+1:]))

Fixed submission:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
maxI = np.argmax(na)
maxA = na[maxI]
nb = np.copy(na)
nb[maxI] = 0
maxA2 = np.max(nb)
for i in range(n):
    if i != maxI:
        print(na[maxI])
    else:
       print(maxA2)

Buggy python submission (verdict: Runtime Error):
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array
for i in range(n):
    print(np.max(a[:i] + a[i+1:]))

Fixed submission:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
maxI = np.argmax(na)
maxA = na[maxI]
nb = np.copy(na)
nb[maxI] = 0
maxA2 = np.max(nb)
for i in range(n):
    if i != maxI:
        print(na[maxI])
    else:
       print(maxA2)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    print(max(a[:i] + a[i+1:]))

Fixed submission:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
maxI = np.argmax(na)
maxA = na[maxI]
nb = np.copy(na)
nb[maxI] = 0
maxA2 = np.max(nb)
for i in range(n):
    if i != maxI:
        print(na[maxI])
    else:
       print(maxA2)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    print(max(a[:i] + a[i+1:]))

Fixed submission:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
na = np.array(a)
maxI = np.argmax(na)
maxA = na[maxI]
nb = np.copy(na)
nb[maxI] = 0
maxA2 = np.max(nb)
for i in range(n):
    if i != maxI:
        print(na[maxI])
    else:
       print(maxA2)
Buggy python submission (verdict: Time Limit Exceeded):
l, r = list(map(int, input().split()))
MOD = 2019
diff = r - l
l = l%MOD
r = l + diff
ans = 2018
for i in range(l,r):
    for j in range(i+1, r+1):
        ans = min(ans, (i%MOD*j%MOD)%MOD )
      
print(ans)

Fixed submission:
l, r = list(map(int, input().split()))
MOD = 2019
diff = r - l
ans = 0
if diff < 2019:
    l = l%MOD
    r = l + diff
    ans = 2018
    for i in range(l,r):
        for j in range(i+1, r+1):
            ans = min(ans, (i%MOD*j%MOD)%MOD )
      
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l, r = list(map(int, input().split()))
MOD = 2019
ans = 2018
for i in range(l,r):
    for j in range(i+1, r+1):
        ans = min(ans, (i%MOD*j%MOD)%MOD )
        
print(ans)

Fixed submission:
l, r = list(map(int, input().split()))
MOD = 2019
diff = r - l
ans = 0
if diff < 2019:
    l = l%MOD
    r = l + diff
    ans = 2018
    for i in range(l,r):
        for j in range(i+1, r+1):
            ans = min(ans, (i%MOD*j%MOD)%MOD )
      
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l, r = list(map(int, input().split()))
MOD = 2019
ans = 2018
for i in range(l,r):
    for j in range(i+1, r+1):
        ans = min(ans, (i%MOD*j%MOD)%MOD )
        
print(ans)

Fixed submission:
l, r = list(map(int, input().split()))
MOD = 2019
diff = r - l
ans = 0
if diff < 2019:
    l = l%MOD
    r = l + diff
    ans = 2018
    for i in range(l,r):
        for j in range(i+1, r+1):
            ans = min(ans, (i%MOD*j%MOD)%MOD )
      
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mina = min(a)
minaindex = a.index(min(a))
if minaindex + 2 <= n:
    ansstartmax = a[minaindex] + a[minaindex+1]
    start = minaindex+1
else:
    ansstartmax = a[minaindex] + a[minaindex-1]
    start = minaindex-1

ans = [0]* (n+1)

for i in range(ansstartmax//2+1):
    ans[start] = i*2
    for j in range(start+1, n+1):
        ans[j] = (a[j-1] - ans[j-1]//2)*2
    
    for j in reversed(range(start)):
        ans[j] = (a[j] - ans[j+1]//2)*2

    
    if ans[0] == ans[-1]:
        print(*ans[:-1])
        break

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

ans = [0]* n
ans[0] = sum(a) - 2*sum(a[1::2])

for i in range(1, n):
    ans[i] = 2*a[i-1] - ans[i-1]

print(*ans)
Buggy python submission (verdict: Runtime Error):
S = input()

A = S[0]
ans = 'No'

if A == S[1]:
    B = S[2]
    if B == S[4]:
        ans = 'Yes'
else:
    B = S[1]
    if A == S[2] and B == S[3]:
        ans = 'Yes'
    if B == S[2] and A == S[3]:
        ans = 'Yes'

print(ans)


Fixed submission:
S = input()

A = S[0]
ans = 'No'

if A == S[1]:
    B = S[2]
    if B == S[3]:
        ans = 'Yes'
else:
    B = S[1]
    if A == S[2] and B == S[3]:
        ans = 'Yes'
    if B == S[2] and A == S[3]:
        ans = 'Yes'

if A == B:
    ans = 'No'

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = [int(_) for _ in input().split()]
import math
MOD = 10**9+7


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,K+1):
    print( (combinations_count(K-1,i-1)*combinations_count(N-K+1,i))%MOD )


Fixed submission:
N, K = [int(_) for _ in input().split()]
import math
MOD = 10**9+7

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,K+1):
    try:
        print( (combinations_count(K-1,i-1)*combinations_count(N-K+1,i))%MOD )
    except:
        print(0)

Buggy python submission (verdict: Runtime Error):
N, K = [int(_) for _ in input().split()]
import math
MOD = 1000000000+7

ans = 0

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,K+1):
    print( (combinations_count(K-1,i-1)*combinations_count(N-K+1,i))%MOD )



Fixed submission:
N, K = [int(_) for _ in input().split()]
import math
MOD = 10**9+7

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,K+1):
    try:
        print( (combinations_count(K-1,i-1)*combinations_count(N-K+1,i))%MOD )
    except:
        print(0)
Buggy python submission (verdict: Runtime Error):
N,X=map(int, input().split()) 
L=list(map(int, input().split())) 
D = 0
for i in range(N):
  D = D + L[i]
  print(L[i])
  if D > X:
    print(i+1)
    break
  if D == X:
    print(i+2)
    break


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

if X < A:
  print(0)
else:
  print(10)

Buggy python submission (verdict: Runtime Error):
N,X=map(int, input().split()) 
L=list(map(int, input().split())) 
D = 0
for i in range(N+1):
  D = D + L[i]
  if D > X:
    print(i+1)
    break


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

if X < A:
  print(0)
else:
  print(10)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

x = [0]*n
y = [0]*n
for i in range(n):
    xx,yy= map(int, input().split())
    x[i] = xx-1
    y[i] = yy-1

from collections import defaultdict
d = defaultdict(lambda:0)

for i in range(n):
    for j in range(n):
        if i==j:continue

        p = x[j]-x[i]
        q = y[j]-y[i]

        d[p*10**9+q] +=1

dv = d.values()
mad =max(dv)

print(n-mad)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

x = [0]*n
y = [0]*n
for i in range(n):
    xx,yy= map(int, input().split())
    x[i] = xx-1
    y[i] = yy-1

if n==1:
    print(1)
    exit()

from collections import defaultdict
d = defaultdict(lambda:0)

for i in range(n):
    for j in range(n):
        if i==j:continue

        p = x[j]-x[i]
        q = y[j]-y[i]

        d[p*10**9+q] +=1

dv = d.values()
mad =max(dv)

print(n-mad)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left


n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()

bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])

cnt = 0
for b, c in bc:
    index = bisect_left(a[cnt:], c)+cnt
    tmp = min(index,b+cnt)
    for i in range(cnt,tmp):
        a[i] = c
    cnt = tmp


print(sum(a))


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left


n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()

bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])

i = 0
for b, c in bc:
    for _ in range(b):
        if c <= a[i]: break
        a[i] = c
        i += 1
        if i >= n :break
    else:
        continue
    break

print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left


n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()

bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])

for b, c in bc:
    index = bisect_left(a, c)
    for i in range(min(index,b)):
        a[i] = c
    a.sort()

print(sum(a))


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left


n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()

bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])

i = 0
for b, c in bc:
    for _ in range(b):
        if c <= a[i]: break
        a[i] = c
        i += 1
        if i >= n :break
    else:
        continue
    break

print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

x, y, z, k = map(int, input().split())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
c = list( map(int, input().split()))

mix_ab= [a_+b_ for a_,b_ in itertools.product(a, b)]
mix_ab.sort(reverse=True)
c.sort(reverse=True)

mix_abc= [ab_+c_ for ab_,c_ in itertools.product(mix_ab[:k], c[:k])]
mix_abc.sort(reverse=True)

print(*mix_abc[:k], sep='\n')

Fixed submission:
import itertools

x, y, z, k = map(int, input().split())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
c = list( map(int, input().split()))

mix_ab= [a_+b_ for a_,b_ in itertools.product(a, b)]
mix_ab.sort(reverse=True)
c.sort(reverse=True)

mix_abc= [ab_+c_ for ab_,c_ in itertools.product(mix_ab[:k], c[:k])]
mix_abc.sort(reverse=True)

print(*mix_abc[:k], sep='\n')

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

import itertools

x, y, z, k = map(int, input().split())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
c = list( map(int, input().split()))

amax = max(a)
a_diff = [a[i]-amax for i in range(0,x)]
bmax = max(b)
b_diff = [b[i]-bmax for i in range(0,y)]
cmax = max(c)
c_diff = [c[i]-cmax for i in range(0,z)]

minus= [a_+b_+c_ for a_,b_,c_ in itertools.product(a_diff, b_diff, c_diff)]
minus.sort(reverse=True)

ans0 = amax+bmax+cmax
for i in range(k):
    ans = ans0 + minus[i]
    print(ans)


Fixed submission:
import itertools

x, y, z, k = map(int, input().split())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
c = list( map(int, input().split()))

mix_ab= [a_+b_ for a_,b_ in itertools.product(a, b)]
mix_ab.sort(reverse=True)
c.sort(reverse=True)

mix_abc= [ab_+c_ for ab_,c_ in itertools.product(mix_ab[:k], c[:k])]
mix_abc.sort(reverse=True)

print(*mix_abc[:k], sep='\n')

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

import itertools

x, y, z, k = map(int, input().split())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
c = list( map(int, input().split()))

amax = max(a)
a_diff = [a[i]-amax for i in range(0,x)]
bmax = max(b)
b_diff = [b[i]-bmax for i in range(0,y)]
cmax = max(c)
c_diff = [c[i]-cmax for i in range(0,z)]

minus= [a_+b_+c_ for a_,b_,c_ in itertools.product(a_diff, b_diff, c_diff)]
minus.sort(reverse=True)

ans0 = amax+bmax+cmax
for i in range(k):
    ans = ans0 + minus[i]
    print(ans)


Fixed submission:
import itertools

x, y, z, k = map(int, input().split())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
c = list( map(int, input().split()))

mix_ab= [a_+b_ for a_,b_ in itertools.product(a, b)]
mix_ab.sort(reverse=True)
c.sort(reverse=True)

mix_abc= [ab_+c_ for ab_,c_ in itertools.product(mix_ab[:k], c[:k])]
mix_abc.sort(reverse=True)

print(*mix_abc[:k], sep='\n')
Buggy python submission (verdict: Runtime Error):
N, Q = map(int, input().split())
s=list(input())
g = [1] * (N + 2)
for i in range(Q):
    Point, RL = input().split()
    for j in range(len(s)):
        if Point == s[j]:
            if RL=="L":
                g[j] = g[j] + g[j+1]
                g[j+1] = 0
            else:
                g[j+2] = g[j+2] + g[j+1]
                g[j+1] = 0
            g[0] = 0
            g[N+1] = 0
print(sum(g))

Fixed submission:
a, b, c=map(int, input().split()) 
if a == b == c:
   print("Yes")
else:
   print("No")
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
d = [0]*n

for i in range(n):
    d[i] = a[i]-b[i]

d.sort()

if sum(d)<0:
    print(-1)
    exit()

cnt_neg = 0
for i in range(n):
    if d[i]<0:cnt_neg+=1

if cnt_neg==0:
    print(0)
    exit()
else:
    ans = cnt_neg

last=n-1
for neg in range(n):
    print(d)
    if d[neg]>=0:break

    while d[neg]<0:
        tmp = min(-d[neg], d[last])
        d[neg] += tmp
        d[last] -= tmp
        if d[last] == 0:
            last-=1
            ans+=1

if d[last] != a[last]-b[last] and d[last]!=0 : ans+=1

print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))
b = list( map(int, input().split()))
d = [0]*n

for i in range(n):
    d[i] = a[i]-b[i]

d.sort()

if sum(d)<0:
    print(-1)
    exit()

cnt_neg = 0
for i in range(n):
    if d[i]<0:cnt_neg+=1

if cnt_neg==0:
    print(0)
    exit()
else:
    ans = cnt_neg

last=n-1
for neg in range(n):
    if d[neg]>=0:break

    while d[neg]<0:
        tmp = min(-d[neg], d[last])
        d[neg] += tmp
        d[last] -= tmp
        if d[last] == 0:
            last-=1
            ans+=1

if d[last] != a[last]-b[last] and d[last]!=0 : ans+=1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, k = map(int, input().split())
h = np.array([int(i) for i in input().split()])

dp = np.array([float('inf')]*n)
dp[0] = 0

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

print(int(dp[-1]))

Fixed submission:
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

# dp=[0 for i in range(N)]
dp = [float("inf")]*(N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])


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

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

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

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

print(dp[-1])


Fixed submission:
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

# dp=[0 for i in range(N)]
dp = [float("inf")]*(N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])


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

Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

# dp=[0 for i in range(N)]
dp = [float("inf")]*(N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])


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


Fixed submission:
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

# dp=[0 for i in range(N)]
dp = [float("inf")]*(N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])


for i in range(N-1):
  for j in range(1, min(K+1, N - i)):
    dp[i+j]=min(dp[i+j], dp[i]+ abs(h[i+j]-h[i]))
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    if j < w[i]:# i番目の荷物の重さw[i]がjを超えているので，入れる可能性がない
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])# 入れ場合と入れない場合を比較
      
print(dp[N][W])

Fixed submission:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j + w[i] <= W:
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i])
      
print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j + w[i] <= W:
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i])
      
print(dp[N][W])

Fixed submission:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j + w[i] <= W:
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i])
      
print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N

for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]

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


Fixed submission:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j + w[i] <= W:
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i])
      
print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
V = sum(v)

dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないのでi番目の荷物を入れる可能性がある
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)

Fixed submission:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
V = sum(v)

dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないのでi番目の荷物を入れる可能性がある
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)