Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def knapsack():
    n, max_w = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for item in list(dp.keys()):
            dp[item+w] = max(dp[item] + v, dp[item+w])
    max_v = 0
    for w, v in dp.items():
        if w <= max_w:
            max_v = max(v, max_v)
    print(max_v)
    

knapsack()

Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

Buggy python submission (verdict: Runtime Error):
def knapsack():
    n, max_w = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for item in list(dp.keys()):
            dp[item+w] = max(dp[item] + v, dp[item+w])
    max_v = 0
    for w, v in dp.items():
        if w <= max_w:
            max_v = max(v, max_v)
    print(max_v)
    
    
knapsack()

Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * N * 1000
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))


Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * N * 1000
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, V-vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))


Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [0] * (W+1)

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        for w in range(W, wi - 1, -1):
            v_ = d[w - wi] + vi
            if v_ > d[w]:
                d[w] = v_
    return d[W]

print(ans(N, W))


Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))