Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify

N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for i in range(N)]
heapify(wv)
wv = [None] + wv

dp = [{0: 0}] + [{} for i in range(N)]

for i in range(1, N+1):
  w, v = wv[i]
  for mw, mv in dp[i-1].items():
    dp[i][mw] = max(dp[i].get(mw, 0), dp[i-1].get(mw, 0))
    if mw + w < W+1:
      dp[i][mw+w] = max(dp[i].get(mw+w, 0), dp[i-1][mw]+v, dp[i-1].get(mw+w, 0))

print(max(dp[N].values()))

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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
N, W = list(map(int, input().split()))

wv = [None] + [list(map(int, input().split())) for i in range(N)]

dp = [{0: 0}] + [{} for i in range(N)]

for i in range(1, N+1):
  w, v = wv[i]
  for mw, mv in dp[i-1].items():
    dp[i][mw] = max(dp[i].get(mw, 0), dp[i-1].get(mw, 0))
    if mw + w < W+1:
      dp[i][mw+w] = max(dp[i].get(mw+w, 0), dp[i-1][mw]+v, dp[i-1].get(mw+w, 0))

print(max(dp[N].values()))


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  from collections import defaultdict
  
  DP = defaultdict(int)
  DP[0] = 0
  
  for w, v in WV:
    for i in reversed(tuple(DP.keys())):
      if i + w <= W:
        DP[i+w] = max(DP[i] + v, DP[i+w])
  return max(DP.values())
  
print(dp_fn())


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    CP = {}
    for i in DP.keys():
      if i + w <= W:
        CP[i+w] = max(DP[i] + v, DP[i])
    for i in CP.keys():
      DP[i] = CP[i]
  return max(DP.values())
  
print(dp_fn())

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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Time Limit Exceeded):
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    for i in reversed(list(DP.keys())):
      if i + w <= W:
        DP[i+w] = max(DP[i] + v, DP[i])
  return max(DP.values())
  
print(dp_fn())


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
WV = (map(int, input().split()) for _ in range(N))

DP = [0] * (W+1)

for w, v in WV:
  for j in range(W, w-1, -1):
    dp = DP[j-w] + v 
    if DP[j] < dp:
      DP[j] = dp
print(max(DP))


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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())