Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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


Fixed submission:
n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])
 
for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Fixed submission:
n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
items = []

append = items.append
for i in range(n):
    append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0] * (w + 1) for _ in range(n + 1)]
    g = [[0] * (w + 1) for _ in range(n + 1)]

    for i in range(w + 1):
        g[0][i] = 1

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)


Fixed submission:
n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
items = []

for i in range(n):
    items.append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1

    for i in range(n + 1):
        c[i][0] = 0

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)


Fixed submission:
n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)