Buggy python submission (verdict: Time Limit Exceeded):
def dfs(item_i, W):
    if item_i >= N:
        return 0
    if visited[item_i][W]:
        return table[item_i][W]
    visited[item_i][W] = True
    if W - w_list[item_i] < 0:
        table[item_i][W] = dfs(item_i+1, W)
    else:
        table[item_i][W] = max(dfs(item_i+1, W), dfs(item_i+1, W-w_list[item_i]) + v_list[item_i])
    
    return table[item_i][W]

N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
table = [[0 for j in range(W+1)]for i in range(N)]
visited = [[False for j in range(W+1)]for i in range(N)]

ans = dfs(0, W)
print(ans)

Fixed submission:
N, maxW = map(int, input().split())
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
def dfs(item_i, W):
    if item_i >= N:
        return 0
    if visited[item_i][W]:
        return table[item_i][W]
    visited[item_i][W] = True
    if W - w_list[item_i] < 0:
        table[item_i][W] = dfs(item_i+1, W)
    else:
        table[item_i][W] = max(dfs(item_i+1, W), dfs(item_i+1, W-w_list[item_i]) + v_list[item_i])
    
    return table[item_i][W]

N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
table = [[0 for j in range(W+1)]for i in range(N)]
visited = [[False for j in range(W+1)]for i in range(N)]

ans = dfs(0, W)
print(ans)

Fixed submission:
N, maxW = map(int, input().split())
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
def rec(depth, w, v):
    if w > maxW:
        return
    WV[depth][w] = max(v, WV[depth][w])
    if depth+1 >= N:
        return
    rec(depth+1, w+W[depth+1], v+V[depth+1])
    rec(depth+1, w, v)


N, maxW = map(int, input().split())
WV = [[-1 for i in range(maxW+1)] for j in range(N)]
W = [0 for i in range(N)]
V = [0 for i in range(N)]
for i in range(N):
    W[i], V[i] = map(int, input().split())
rec(0, 0, 0)
rec(0, W[0], V[0])
print(max(WV[-1]))


Fixed submission:
N, maxW = map(int, input().split())
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
def rec(depth, w, v):
    if w > maxW:
        return
    WV[depth][w] = max(v, WV[depth][w])
    if depth+1 >= N:
        return
    rec(depth+1, w+W[depth+1], v+V[depth+1])
    rec(depth+1, w, v)


N, maxW = map(int, input().split())
WV = [[-1 for i in range(maxW+1)] for j in range(N)]
W = [0 for i in range(N)]
V = [0 for i in range(N)]
for i in range(N):
    W[i], V[i] = map(int, input().split())
rec(0, 0, 0)
rec(0, W[0], V[0])
print(max(WV[-1]))


Fixed submission:
N, maxW = map(int, input().split())
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))