Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
f = [10**9 for x in range(X + 1)]
f[0] = 0
for n in range(N):
    f = [
        min(f[x], f[x - V[n]] + W[n]) if x >= V[n] else f[x]
        for x in range(X + 1)
    ]
for x in range(X + 1)[::-1]:
    if f[x] <= M:
        print(x)
        exit()


Fixed submission:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)


Fixed submission:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def f(n, m):
    if n < 1 or m < 1:
        return 0
    elif m < W[n - 1]:
        return f(n - 1, m)
    else:
        return max(f(n - 1, m), f(n - 1, m - W[n - 1]) + V[n - 1])


N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
print(f(N, M))


Fixed submission:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def f(n, m):
    if n < 1 or m < 1:
        return 0
    elif m < W[n - 1]:
        return f(n - 1, m)
    else:
        return max(f(n - 1, m), f(n - 1, m - W[n - 1]) + V[n - 1])


N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
print(f(N, M))


Fixed submission:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)