Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
A.sort()
p = N//2
ans =sum(A[p:])-sum(A[:p])
hoge = ans
for i in range(p,N-1):
    hoge -= A[i]*2
    if hoge > ans:
        p = i
        ans = hoge
print(ans)
B=[0]*N
l =0
hoge = A[p+1]
for i in range(p+2,N):
    print(A[l],hoge)
    hoge = A[l]-hoge
    l += 1
    print(A[i],hoge)
    hoge = A[i]-hoge
for i in range(l,p+1):
    print(hoge,A[i])
    hoge -= A[i]



Fixed submission:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
hoge = sum(A)
p = 0
for i in range(N-1):
    hoge -= A[i]*2
    if hoge > ans:
        ans = hoge
        p = i
print(ans)
hoge = A[0]
for i in range(p+1,N-1):
    print(hoge,A[i])
    hoge -= A[i]
print(A[N-1],hoge)
hoge = A[N-1] - hoge
for i in range(1,p+1):
    print(hoge,A[i])
    hoge -= A[i]

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
A.sort()
p = N//2
ans =sum(A[p:])-sum(A[:p])
hoge = ans
for i in range(p,N-1):
    hoge -= A[i]*2
    if hoge > ans:
        p = i
        ans = hoge
print(hoge)
B=[0]*N
l =0
hoge = A[p+1]
for i in range(p+2,N):
    print(A[l],hoge)
    hoge = A[l]-hoge
    l += 1
    print(A[i],hoge)
    hoge = A[i]-hoge
for i in range(l,p+1):
    print(hoge,A[i])
    hoge -= A[i]

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
hoge = sum(A)
p = 0
for i in range(N-1):
    hoge -= A[i]*2
    if hoge > ans:
        ans = hoge
        p = i
print(ans)
hoge = A[0]
for i in range(p+1,N-1):
    print(hoge,A[i])
    hoge -= A[i]
print(A[N-1],hoge)
hoge = A[N-1] - hoge
for i in range(1,p+1):
    print(hoge,A[i])
    hoge -= A[i]

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
A.sort()
nega = []
for i in range(N):
    if A[0] < 0:
        nega.append(A.pop(0))
    else:
        break
N = len(A)
print( sum(A[N//2:]) - sum(A[:N//2]) - sum(nega))
B = [0]*N
l,r = 0,N-1
for i in range(N):
    if i%2 == 0:
        B[i] = A[r]
        r -= 1
    else:
        B[i] = A[l]
        l += 1
hoge = B[-1]
for i in range(N-1):
    print(B[N-i-2],hoge)
    hoge = B[N-i-2]-hoge
for i in nega:
    print(hoge,i)
    hoge -= i

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
hoge = sum(A)
p = 0
for i in range(N-1):
    hoge -= A[i]*2
    if hoge > ans:
        ans = hoge
        p = i
print(ans)
hoge = A[0]
for i in range(p+1,N-1):
    print(hoge,A[i])
    hoge -= A[i]
print(A[N-1],hoge)
hoge = A[N-1] - hoge
for i in range(1,p+1):
    print(hoge,A[i])
    hoge -= A[i]
Buggy python submission (verdict: Runtime Error):
N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")

Fixed submission:
import sys
sys.setrecursionlimit(2000000)

N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")
Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
V = list(map(int,input().split()))
L,R = [0]*(K),[0]*(K)
L[0] = max(0,V[0])
R[0] = max(0,V[-1])
for i in range(min(N,K)+1):
    part = V[:i]
    part.sort()
    for j in range(min(K-i,i)):
        if part[0] < 0:
            part.pop(0)
        L[i+j] = max(L[i+j],sum(part))
V.reverse()
for i in range(min(N,K)+1):
    part = V[:i]
    part.sort()
    for j in range(min(K-i,i)):
        if part[0] < 0:
            part.pop(0)
        R[i+j] = max(R[i+j],sum(part))
R[-1] = max(0,sum(part())
ans = max(R[-1],L[-1])
for i in range(K-1):
    ans = max(ans,L[i]+R[-i-2])
print(L)
print(R)
print(ans)

Fixed submission:
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = 0
for i in range(min(N,K)+1): # Dequeueからとる宝石の数
    for j in range(i+1):  # 左からとる宝石の数
        Juel = V[:j]+V[N-i+j:]
        Juel.sort()
        sum_v = 0
        for k in range(min(K-i,i)):
            Juel[k] = max(Juel[k],0)
        ans = max(ans,sum(Juel))
print(ans)

Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
D = list(map(int,input().split()))
L, R = [0]*(K),[0]*K
for i in range(K+1):
    tmp = D[:i]
    tmp.sort()
    X = sum(tmp)
    for j in range(min(K-i,i)):
        if tmp[0] < 0:
            X-=tmp.pop(0)
        else:
            L[i+j] = max(L[i+j],X)
            break
        L[i+j] = max(L[i+j],X)

for i in range(K+1):
    tmp = D[N-i:]
    tmp.sort()
    X = sum(tmp)
    for j in range(min(K-i,i)):
        if tmp[0] < 0:
            X-=tmp.pop(0)
        else:
            R[i+j] = max(R[i+j],X)
            break
        R[i+j] = max(R[i+j],X)

ans = []
for i in range(K):
    ans.append(L[i]+R[-i-1])
print(max(ans))

Fixed submission:
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = 0
for i in range(min(N,K)+1): # Dequeueからとる宝石の数
    for j in range(i+1):  # 左からとる宝石の数
        Juel = V[:j]+V[N-i+j:]
        Juel.sort()
        sum_v = 0
        for k in range(min(K-i,i)):
            Juel[k] = max(Juel[k],0)
        ans = max(ans,sum(Juel))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = list(list(map(int,input().split())) for i in range(M))
for B,C in BC:
    A.sort()
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break
print(sum(A))

Fixed submission:
N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = list(list(map(int,input().split())) for i in range(M))
A.sort()
BC = sorted(BC,key = lambda x:x[1],reverse = True)
X = []

for B,C in BC:
    for i in range(min(B,N-len(X))):
        X.append(C)
ans = [sum(A)]
p = len(X)
for i in range(p):
    ans.append(ans[-1]+X[i]-A[i])
print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
H,W = map(int,input().split())
A =[]
for i in range(H):
    A.append([1 if i == "#" else 0 for i in list(input())])
que = []
A = np.array(A)
for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            que.append([i,j])
for ans in range(H+W):
    flag = 0
    tmp = []

    for _ in range(len(que)):
        i,j = que.pop()
        # 上
        if not i == 0:
            if A[i-1][j] == 0:
                A[i-1][j] = 1
                flag = 1
                tmp.append([i-1,j])
        # 下
        if not i == H-1:
            if A[i+1][j] == 0:
                A[i+1][j] = 1
                flag = 1
                tmp.append([i+1,j])
        # 左
        if not j == 0:
            if A[i][j-1] == 0:
                A[i][j-1] = 1
                flag = 1
                tmp.append([i,j-1])
        # 右
        if not j == W-1:
            if A[i][j+1] == 0:
                A[i][j+1] = 1
                flag = 1
                tmp.append([i,j+1])
    if flag == 0:
        break
    que = tmp.copy()
print(ans)

Fixed submission:
import numpy as np
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "#" else H+W for i in list(input())])
A = np.array(A)
for i in range(H-1):
    A[i+1,:] = np.minimum(A[i,:]+1,A[i+1,:])
for i in range(H-1,0,-1):
    A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
    A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
    A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))

Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int,input().split())
A =[]
for i in range(H):
    A.append([1 if i == "#" else 0 for i in list(input())])
que = []
for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            que.append([i,j])
for ans in range(H+W):
    flag = 0
    tmp = []

    for _ in range(len(que)):
        i,j = que.pop()
        # 上
        if not i == 0:
            if A[i-1][j] == 0:
                A[i-1][j] = 1
                flag = 1
                tmp.append([i-1,j])
        # 下
        if not i == H-1:
            if A[i+1][j] == 0:
                A[i+1][j] = 1
                flag = 1
                tmp.append([i+1,j])
        # 左
        if not j == 0:
            if A[i][j-1] == 0:
                A[i][j-1] = 1
                flag = 1
                tmp.append([i,j-1])
        # 右
        if not j == W-1:
            if A[i][j+1] == 0:
                A[i][j+1] = 1
                flag = 1
                tmp.append([i,j+1])
    if flag == 0:
        break
    que = tmp.copy()
print(ans)

Fixed submission:
import numpy as np
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "#" else H+W for i in list(input())])
A = np.array(A)
for i in range(H-1):
    A[i+1,:] = np.minimum(A[i,:]+1,A[i+1,:])
for i in range(H-1,0,-1):
    A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
    A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
    A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    tmp = x%y
    while not tmp == 0:
        x = y
        y = tmp
        tmp = x%y
    return y
N = int(input())
A = list(map(int,input().split()))

gcd_max = 0
for i in range(N):
    tmp = A[0]
    if i == 0:
        tmp = A[1]
    for j in range(N):
        if not j == i:
            tmp = gcd(tmp,A[j])
    if tmp > gcd_max:
        gcd_max = tmp
print(gcd_max)

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

def GCD(x,y):
    while y != 0:
        x,y = y,x%y
    return x

l,r = [0],[0]
for i in range(N-1):
    l.append(GCD(l[-1],A[i]))
    r.append(GCD(r[-1],A[N-i-1]))

ans = 0
for i in range(N):
    ans = max(ans,GCD(l[i],r[N-i-1]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
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()))
AB = []
ABC = []
for i in A:
    for j in B:
        AB.append(i+j)
AB.sort(reverse = True)
for i in AB[:K+1]:
    for j in C:
        ABC.append(i+j)
ABC.sort(reverse = True)
for i in range(K):
    print(ABC[i])

Fixed submission:
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()))
AB = []
ABC = []
for i in A:
    for j in B:
        AB.append(i+j)
AB.sort(reverse = True)
for i in AB[:K+1]:
    for j in C:
        ABC.append(i+j)
ABC.sort(reverse = True)
for i in range(K):
    print(ABC[i])
Buggy python submission (verdict: Runtime Error):
N = int(input())
B = list(map(int,input().split()))

def func(B,i,C):
    if(C[0:i].count(True) + 1 == B[i]): #左の入力済みを数える
        print(B[i])
        C[i] = True
        next = -1
        for j in range(N-1,-1,-1):
            if C[j] == False:
                next = j
                break
        if next == -1:
            return
        func(B,next,C)
    else:
        next = i - 1
        for j in range(i-1,-1,-1):
            if C[j] == False:
                next = j
                break
        func(B,next,C)

flag = 0
for i in range(N):
    if B[i] > i + 1:
        flag = -1
        break

if(flag == -1):
    print(-1)
else:
    C = [False] * N
    func(B,N-1,C)

Fixed submission:
N = int(input())
b = list(map(int,input().split()))
tmp = b[:]
ans = []
i = N-1
while i >= 0:
    if tmp[i] == 1:
        tmp[i] = float('inf')
        ans.append(b[i])
        while i < N:
            tmp[i] -= 1
            i += 1
    i -= 1
if len(ans) == N:
    for i in ans:
        print(i)
else:
    print(-1)

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

def func(B,i,C):
    if(C[0:i].count(True) + 1 >= B[i]): #左の入力済みを数える
        print(B[i])
        C[i] = True
        next = -1
        for j in range(N-1,-1,-1):
            if C[j] == False:
                next = j
                break
        if next == -1:
            return
        func(B,next,C)
    else:
        for next in range(i-1,-1,-1):
            if C[j] == False:
                func(B,next,C)
                break
        

flag = 0
for i in range(N):
    if B[i] > i + 1:
        flag = -1
        break

if(flag == -1):
    print(-1)
else:
    C = [False] * N
    func(B,N-1,C)

Fixed submission:
N = int(input())
b = list(map(int,input().split()))
tmp = b[:]
ans = []
i = N-1
while i >= 0:
    if tmp[i] == 1:
        tmp[i] = float('inf')
        ans.append(b[i])
        while i < N:
            tmp[i] -= 1
            i += 1
    i -= 1
if len(ans) == N:
    for i in ans:
        print(i)
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
B = list(map(int,input().split()))
B_copy = B.copy

def func(B,i,C):
    if(C[0:i].count(True) + 1 == B[i]):
        print(B[i])
        C[i] = True
        next = -1
        for j in range(N-1,-1,-1):
            if C[j] == False:
                next = j
                break
        if next == -1:
            return
        func(B,next,C)
    else:
        next = -1
        for j in range(i-1,-1,-1):
            if C[j] == False:
                next = j
                break
        func(B,next,C)

flag = 0
for i in range(N):
    if B[i] > i + 1:
        flag = -1
        break

if(flag == -1):
    print(-1)
else:
    C = [False] * N
    func(B,N-1,C)
        



Fixed submission:
N = int(input())
b = list(map(int,input().split()))
tmp = b[:]
ans = []
i = N-1
while i >= 0:
    if tmp[i] == 1:
        tmp[i] = float('inf')
        ans.append(b[i])
        while i < N:
            tmp[i] -= 1
            i += 1
    i -= 1
if len(ans) == N:
    for i in ans:
        print(i)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
bri = [[int(i) for i in input().split()]for i in range(M)]

def benri(x,con):
    #conにxが含まれていたらconを返す
    if x in con :
        return con
    else:
        con.append(x)
    #探索するよ
    for i in bri:
        if x in i:
            con=(benri(i[i[0]==x],con))
    return con

for i in range(1,M+1):
    bri.pop(0)
    #不便さを図るよ
    sima = []
    fuben = []
    for j in range(1,N+1):
        if not(j in sima):
            #simaからbenriを排除
            fubencount = 0
            AAA = benri(j,[])
            for k in AAA:
                sima.append(k)
            fuben.append(len(AAA))
    fubendo = 0
    
    f = int((N*(N-1))/2)
    for j in fuben:
        f -=int ((j*(j-1))/2)
    print(int(f))


Fixed submission:
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(M))
AB.reverse()
node = [[i,[i]]for i in range(N)]
ans = [(N*(N-1))//2]
for a,b in AB:
    a,b = min(node[a-1][0],node[b-1][0]),max(node[a-1][0],node[b-1][0])
    if a != b:
        ans.append(ans[-1]-len(node[a][1])*len(node[b][1]))
        for i in node[b][1]:
            node[i][0] = a
            node[i][1] = [i]
            node[a][1].append(i)
    else:
        ans.append(ans[-1])
ans.reverse()

for i in ans[1:]:
    print(i)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
bri = [[int(i) for i in input().split()]for i in range(M)]

def benri(x,con):
    #conにxが含まれていたらconを返す
    if x in con :
        return con
    else:
        con.append(x)
    #探索するよ
    for i in bri:
        if x in i:
            con=(benri(i[i[0]==x],con))
    return con

for i in range(1,M+1):
    bri.pop(0)
    #不便さを図るよ
    sima = []
    fuben = []
    for j in range(1,N+1):
        if not(j in sima):
            #simaからbenriを排除
            fubencount = 0
            AAA = benri(j,[])
            for k in AAA:
                sima.append(k)
            fuben.append(len(AAA))
    fubendo = 0
    
    f = (N*(N-1))/2
    for j in fuben:
        f -= (j*(j-1))/2
    print(f)


Fixed submission:
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(M))
AB.reverse()
node = [[i,[i]]for i in range(N)]
ans = [(N*(N-1))//2]
for a,b in AB:
    a,b = min(node[a-1][0],node[b-1][0]),max(node[a-1][0],node[b-1][0])
    if a != b:
        ans.append(ans[-1]-len(node[a][1])*len(node[b][1]))
        for i in node[b][1]:
            node[i][0] = a
            node[i][1] = [i]
            node[a][1].append(i)
    else:
        ans.append(ans[-1])
ans.reverse()

for i in ans[1:]:
    print(i)
Buggy python submission (verdict: Runtime Error):
N = int(input())
x = []
u = []
Y = 0
for i in range(N):
    s = [i for i in input().split()]
   	x.append(float(s[0]))
    u.append(s[1])

    if u[i] == 'BTC':
        Y += x[i]*380000
    else:
        Y += x[i]

print(Y)

Fixed submission:
N = int(input())
x = []
u = []
Y = 0
for i in range(N):
    s = [i for i in input().split()]
    x.append(float(s[0]))
    u.append(s[1])

    if u[i] == 'BTC':
        Y += x[i]*380000
    else:
        Y += x[i]

print(Y)
Buggy python submission (verdict: Runtime Error):
#入力
N,M = map(int,input().split())
X = [int(i) for i in input().split()]
#ソートする
X.sort()

L = list()
for i in range(M-1):
    L.append(X[i+1]-X[i])
a=0
L.sort()
for i in range(N-1):
    L.pop(-1)
for i in L:
    a+=i
print(a)

Fixed submission:
#入力
N,M = map(int,input().split())
X = [int(i) for i in input().split()]
#ソートする
X.sort()
if N>=M:
    print("0")
else:
    L = list()
    for i in range(M-1):
        L.append(X[i+1]-X[i])
    a=0 
    L.sort()
    for i in range(N-1):
        L.pop(-1)
    for i in L:
        a+=i
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N, M = map(int,input().split())
root = [1]*N
side = [[]for i in range(N)]

for i in range(N+M-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    root[b-1] = 0

queue = deque([root.index(1)])
cost = [0]*N
oya = [0]*N
while queue:
    q = queue.popleft()
    for i in side[q]:
        if cost[i] <= cost[q]:
            cost[i] = cost[q]+1
            oya[i] = q+1
            queue.append(i)

for i in oya:
    print(i)


Fixed submission:
from collections import deque

N, M = map(int,input().split())
count = [0]*N
side = [[]for i in range(N)]
rside = [[]for i in range(N)]

for i in range(N+M-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    rside[b-1].append(a-1)
    count[b-1] += 1
root = count.index(0)
queue = deque([root])
top = [0]*N

for i in range(N):
    q = queue.popleft()
    top[q] = i
    for k in side[q]:
        count[k] -= 1
        if count[k] == 0:
            queue.append(k)
for i in range(N):
    if rside[i] == []:
        print(0)
        continue
    ret = root
    for j in rside[i]:
        if top[ret] < top[j]:
            ret = j
    print(ret+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(0,N):
    for j in range(i+1,min(N,i+K+1)):
        DP[j] = min(DP[j],DP[i]+abs(h[i]-h[j]))
print(DP[-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(N):
    for j in range(K):
        if i+j+1 < N:
            DP[i+1+j] = min(DP[i+j+1],DP[i]+abs(h[i]-h[i+j+1]))
print(DP[-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):
        if i+j+1 < N:
            DP[i+1+j] = min(DP[i+j+1],DP[i]+abs(h[i]-h[i+j+1]))
print(DP[-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(N):
    for j in range(K):
        if i+j+1 < N:
            DP[i+1+j] = min(DP[i+j+1],DP[i]+abs(h[i]-h[i+j+1]))
print(DP[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]

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

Fixed submission:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-1])

Fixed submission:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*1000+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*1000+1):
        if j < v:
            DP[i+1][j] = DP[i][j] 
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
for i in range(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break

Fixed submission:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*1000+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*1000+1):
        if j < v:
            DP[i+1][j] = DP[i][j] 
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
for i in range(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break