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

N, W = map(int, input().split())

dp = defaultdict(int)
dp[0] = 0
idx2check = {0}
for _ in range(N):
    w, v = map(int, input().split())
    new_idx2check = set()
    for k in idx2check:
        dp[k + w] = max(dp[k + w], dp[k] + v)
        new_idx2check.add(k+w)

    idx2check |= new_idx2check

ans = 0
for k, v in dp.items():
    if k <= W:
        ans = max(ans, v)

print(ans)


Fixed submission:
from collections import defaultdict

N, W = map(int, input().split())

dp = defaultdict(lambda: 1e9)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    keys = sorted(dp.keys(), reverse=True)
    for k in keys:
        dp[k + v] = min(dp[k + v], dp[k] + w)
        if dp[k + v] <= W:
            ans = max(ans, k + v)


print(ans)

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

N, W = map(int, input().split())

dp = defaultdict(int)
dp[0] = 0
idx2check = [0]
for _ in range(N):
    w, v = map(int, input().split())
    new_idx2check = []
    for k in idx2check:
        dp[k + w] = max(dp[k + w], dp[k] + v)
        new_idx2check.append(k+w)

    idx2check += new_idx2check

ans = 0
for k, v in dp.items():
    if k <= W:
        ans = max(ans, v)

print(ans)


Fixed submission:
from collections import defaultdict

N, W = map(int, input().split())

dp = defaultdict(lambda: 1e9)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    keys = sorted(dp.keys(), reverse=True)
    for k in keys:
        dp[k + v] = min(dp[k + v], dp[k] + w)
        if dp[k + v] <= W:
            ans = max(ans, k + v)


print(ans)

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

N, W = map(int, input().split())

dp = defaultdict(int)
dp[0] = 0
idx2check = [0]
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    new_idx2check = []
    for k in idx2check:
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            ans = max(ans, dp[k + w])
            new_idx2check.append(k+w)

    idx2check += new_idx2check


print(ans)


Fixed submission:
from collections import defaultdict

N, W = map(int, input().split())

dp = defaultdict(lambda: 1e9)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    keys = sorted(dp.keys(), reverse=True)
    for k in keys:
        dp[k + v] = min(dp[k + v], dp[k] + w)
        if dp[k + v] <= W:
            ans = max(ans, k + v)


print(ans)

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

N, W = map(int, input().split())

dp = defaultdict(int)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in list(dp.keys()):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            ans = max(ans, dp[k + w])


print(ans)


Fixed submission:
from collections import defaultdict

N, W = map(int, input().split())

dp = defaultdict(lambda: 1e9)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    keys = sorted(dp.keys(), reverse=True)
    for k in keys:
        dp[k + v] = min(dp[k + v], dp[k] + w)
        if dp[k + v] <= W:
            ans = max(ans, k + v)


print(ans)

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

N, W = map(int, input().split())

dp = defaultdict(int)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in list(dp.keys()):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            ans = max(ans, dp[k + w])


print(ans)


Fixed submission:
from collections import defaultdict

N, W = map(int, input().split())

dp = defaultdict(lambda: 1e9)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    keys = sorted(dp.keys(), reverse=True)
    for k in keys:
        dp[k + v] = min(dp[k + v], dp[k] + w)
        if dp[k + v] <= W:
            ans = max(ans, k + v)


print(ans)