Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def args():
    N, M = map(int, input().split())

    ST = []
    for _ in range(N):
        ST.append(tuple(map(int, input().split())))

    CP = []
    for _ in range(M):
        CP.append(tuple(map(int, input().split())))

    # print(N, M)
    # print(ST)
    # print(CP)

    return N, M, ST, CP


def solve(N, M, ST, CP):
    def get_dist(xy1, xy2):
        x1, y1 = xy1
        x2, y2 = xy2

        return abs(x1 - x2) + abs(y1 - y2)

    res = []
    for st in ST:
        min_cp, min_dist = None, 1000
        for i, cp in enumerate(CP):
            dist = get_dist(st, cp)
            if dist < min_dist:
                min_dist = dist
                min_cp = i
        res.append(min_cp + 1)

    return res


if __name__ == '__main__':
    ans = solve(*args())
    for a in ans:
        print(a)


Fixed submission:
def args():
    N, M = map(int, input().split())

    ST = []
    for _ in range(N):
        ST.append(tuple(map(int, input().split())))

    CP = []
    for _ in range(M):
        CP.append(tuple(map(int, input().split())))

    # print(N, M)
    # print(ST)
    # print(CP)

    return N, M, ST, CP


def solve(N, M, ST, CP):
    def get_dist(xy1, xy2):
        x1, y1 = xy1
        x2, y2 = xy2

        return abs(x1 - x2) + abs(y1 - y2)

    res = []
    for st in ST:
        min_cp, min_dist = 0, float("inf")
        for i, cp in enumerate(CP):
            dist = get_dist(st, cp)
            if dist < min_dist:
                min_dist = dist
                min_cp = i
        res.append(min_cp + 1)

    return res


if __name__ == '__main__':
    ans = solve(*args())
    for a in ans:
        print(a)
Buggy python submission (verdict: Runtime Error):
import math
import collections
import functools

def solve():
    N = int(input())
    P = 10**9+7

    fn = math.factorial(N)

    c = collections.Counter(prime_factorize(fn))
    
    ans = functools.reduce(lambda x, y: x * y, map(lambda x: x + 1, c.values()))

    return ans % P


def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res


if __name__ == '__main__':
    res = solve()
    print(res)


Fixed submission:
import math
import collections
import functools


def solve():
    N = int(input())
    P = 10**9+7

    if N == 1:
        return 1

    fn = math.factorial(N)

    divisors = prime_factorize(fn)

    c = collections.Counter(divisors)

    ans = functools.reduce(lambda x, y: x * y, map(lambda x: x + 1, c.values()))

    return ans % P


def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res


if __name__ == '__main__':
    res = solve()
    print(res)
Buggy python submission (verdict: Runtime Error):
def solve():
    S = input()
    # print(S, len(S))

    S = S[::-1]
    words = ("dream"[::-1], "dreamer"[::-1], "erase"[::-1], "eraser"[::-1])

    def recur(i):
        if i >= len(S):
            return True

        for word in words:
            if S[i:i + len(word)] == word:
                if recur(i + len(word)):
                    return True
        return False

    ans = recur(0)

    return ans


if __name__ == '__main__':
    res = solve()
    if res:
        print("YES")
    else:
        print("NO")


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    S = input()
    # print(S, len(S))

    words = {0: "dream", 1: "dreamer", 2: "erase", 3: "eraser"}

    TABLE = [[-1 for x in range(len(S) + 1)] for y in range(len(words) + 1)]

    def recur(i, w):
        if not TABLE[w][i] == -1:
            return TABLE[w][i]

        if i >= len(S):
            # print("jey", log)
            return True

        r1, r2, r3, r4 = False, False, False, False
        if S[i:i + 5] == words[0]:
            r1 = recur(i + 5, 0)
        if S[i:i + 7] == words[1]:
            r2 = recur(i + 7, 1)
        if S[i:i + 5] == words[2]:
            r3 = recur(i + 5, 2)
        if S[i:i + 6] == words[3]:
            r4 = recur(i + 6, 3)

        TABLE[w][i] = r1 or r2 or r3 or r4 or False

        return TABLE[w][i]

    ans = recur(0, 0)

    return ans


if __name__ == '__main__':
    res = solve()
    if res:
        print("YES")
    else:
        print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, T = tuple(map(int, input().split()))
    AS = tuple(map(int, input().split()))

    # print(N, T)
    # print(AS)

    m = -float('inf')
    c = 0
    for i in range(len(AS)):
        for x in range(i + 1, len(AS)):
            # max が見つかったら max を更新し, counter を 1 にリセット
            d = AS[x] - AS[i]
            if m < d:
                m = d
                c = 1
            elif m == d: # max と同じ値なら counter を ++
                c += 1
    
    return c


if __name__ == '__main__':
    res = solve()
    print(res)


Fixed submission:
import heapq

def solve():
    N, T = tuple(map(int, input().split()))
    AS = tuple(map(int, input().split()))

    # print(N, T)
    # print(AS)

    lis = []
    D = {}

    m = -float('inf')
    c = 0
    for i in range(len(AS) - 1, -1, -1):
        x = AS[i]
        heapq.heappush(lis, -x)
        D[i] = -lis[0]

    for i in range(len(AS)):
        x = AS[i]

        d = D[i] - AS[i]
        if d > 0:
            if m < d:
                m = d
                c = 1
            elif m == d:  # max と同じ値なら counter を ++
                c += 1

    return c


if __name__ == '__main__':
    res = solve()
    print(res)
Buggy python submission (verdict: Runtime Error):
def solve():
    def recur(i, n, total):
        # print("i, n, total", i, n, total)

        if not TABLE[i][n][total] == -1:
            # print('cache!')
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                return 1
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        # print(ans1, ans2)

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


if __name__ == '__main__':
    print(solve())


Fixed submission:
args = []
for _ in range(4):
    args.append(int(input()))

N, K, X, Y = args


def solve():
    if N <= K:
        return N * X

    first = K
    second = N - first

    return first * X + second * Y

res = solve()
print(res)

Buggy python submission (verdict: Runtime Error):
def solve():
    def recur(i, n, total):
        # print("i, n, total", i, n, total)

        if not TABLE[i][n][total] == -1:
            # print('cache!')
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                TABLE[i][n][total] = 1
                return 1
            TABLE[i][n][total] = 0
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        # print(ans1, ans2)

        return ans1 + ans2

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


if __name__ == '__main__':
    print(solve())


Fixed submission:
args = []
for _ in range(4):
    args.append(int(input()))

N, K, X, Y = args


def solve():
    if N <= K:
        return N * X

    first = K
    second = N - first

    return first * X + second * Y

res = solve()
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, A, B = list(map(int, input().split()))

def combinations_count(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def solve():
    # print(H, W, A, B)

    goal = W - 1, H - 1

    # 境界点
    nx = B - 1
    ny = H - A

    # 境界点から斜め右上の点から, y=0 へ伸びる線が choke point
    c_bottom = nx + 1, ny - 1
    # print(c_bottom)
    choke_points = []
    combs = []

    for i in range(c_bottom[1], -1, -1):
        choke_points.append((c_bottom[0], i))

    for i in range(len(choke_points)):
        x, y = choke_points[i]
        if i == len(choke_points) - 1:
            combs.append(combinations_count(x + y, x))
        else:
            combs.append(combinations_count((x + y) - 1, x - 1))

    for i in range(len(choke_points)):
        x, y = choke_points[i]
        dx, dy = goal[0] - x, goal[1] - y
        combs[i] *= combinations_count(dx + dy, dx)

    # print(sum(combs))
    res = sum(combs) % (10 ** 9 + 7)
    return res
  

res = solve()
print(res)


Fixed submission:
H, W, A, B = list(map(int, input().split()))
 
# 事前計算 + 演算ごとに mod する
def solve():
    # 組合せの計算用に階乗を事前計算しておく
    MOD = 10 ** 9 + 7
    FACT = [0] * (H + W + 1)
    INV_FACT = [0] * (H + W + 1)  # 逆元. 組合せの計算ごとにMODを取るため
 
    FACT[0], INV_FACT[0] = 1, 1
    for i in range(1, (H + W + 1)):
        FACT[i] = (FACT[i - 1] * i) % MOD
        INV_FACT[i] = pow(FACT[i], MOD - 2, MOD)  # フェルマーの小定理を使う
 
    def mod_nCr(n, r):
        if n < r or n == 0 or r == 0:
            return 1
 
        return FACT[n] * (INV_FACT[r] * INV_FACT[n - r]) % MOD
 
    # print(H, W, A, B)
 
    # 座標は(x, y). startは(0, 0)
    goal = W - 1, H - 1
 
    # 境界点: 移動できないエリアの右上の点
    nx = B - 1
    ny = H - A
 
    # 境界点から右斜め上に1つ移動した点(choke_left)から, 右端へ伸びる線がchoke points
    choke_left = nx + 1, ny - 1
 
    choke_points = []
    for i in range(B, W):
        choke_points.append((i, choke_left[1]))
 
    # 組合せを計算する: startからcp1, cp2からgoalまで組合せを掛ける
    ans = 0
    for cp1 in choke_points:
        x, y = cp1
        from_start_to_cp1 = mod_nCr(x + y, x)
 
        # cp1から1つ下の点がcp2
        y += 1
        dx, dy = goal[0] - x, goal[1] - y
        from_cp2_to_goal = mod_nCr(dx + dy, dx)
 
        ans = ans % MOD + (from_start_to_cp1 * from_cp2_to_goal % MOD) % MOD
 
    return ans % MOD
 
res = solve()
print(res)
Buggy python submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

for i in range(n):
	for j in range(i+1,i+2+1):
      if j<n:
        dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
        
print(dp[n-1])

Fixed submission:
import sys
n = int(input())

a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0] = 0
for i in range(n):
  for j in range(i+1,i+2+1):
    if j<n:
      dp[j]= min(dp[j],dp[i]+abs(a[i]-a[j]))
      
      
print(dp[n-1])

Buggy python submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

for i in range(n):
	for j in range(i+1,i+2+1):
      if j<n:
        dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
        
print(dp[n-1])

Fixed submission:
import sys
n = int(input())

a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0] = 0
for i in range(n):
  for j in range(i+1,i+2+1):
    if j<n:
      dp[j]= min(dp[j],dp[i]+abs(a[i]-a[j]))
      
      
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,k = map(int,input().split())

a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0] = 0
for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j]= min(dp[j],dp[i]+abs(a[i]-a[j]))
      
      
print(dp[n-1])


Fixed submission:
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

#print(dp)
for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
  #print(dp)
      
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))

      
print(dp[n-1])


Fixed submission:
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

#print(dp)
for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
  #print(dp)
      
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0


for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
      
print(dp[n-1])

Fixed submission:
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

#print(dp)
for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
  #print(dp)
      
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

#print(dp)
for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
  #print(dp)
      
print(dp[n-1])

Fixed submission:
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))

dp = [sys.maxsize]*n
dp[0]=0

#print(dp)
for i in range(n):
  for j in range(i+1,i+k+1):
    if j<n:
      dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
  #print(dp)
      
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):

def knapsack(n,c,w,v):
  if n == 0 or c == 0:
    return n
  if w[n] > c:
    return knapsack(n-1,c,w,v)
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v)
    opt2 = knapsack(n-1,c,w,v)
    return max(opt1,opt2)


n,c = map(int,input().split())

w = [-1]; v = [-1]

for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v)
print(result)        
        
        

Fixed submission:
n ,c = map(int,input().split())
wt =[]; val=[]

for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  
# dp [n][c+1] = 0 
dp = [[0 for i in range(c+1)]for j in range(n)]

for w in range(c+1):
  wi = wt[0]
  if wi<=w:
    dp[0][w]=val[0]
  else:
    dp[0][0]=0

for i in range(1,n):
  wi = wt[i];vi = val[i]
  for w in range(1,c+1):
    if wi<=w:
      dp[i][w] = max(vi+dp[i-1][w-wi] , dp[i-1][w])
    else:
      dp[i][w] = dp[i-1][w]

print(dp[n-1][c])
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10**9)

n , m = map(int,input().split())

g = [[] for i in range(n)]

for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
  
# finding longest path for vertice i
def dfs(i):
  temp = 0
  for nv in g[i]:
    temp = max(temp, dfs(nv)+1)
    
  return temp
  
# finding overall longest path  
res = 0  
for i in range(n):
  res = max(res, dfs(i))
  
print(res)

Fixed submission:
import sys

sys.setrecursionlimit(10**9)

n , m = map(int,input().split())

g = [[] for i in range(n)]

dp = [-1] *n
for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
  
# finding longest path for vertice i
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp = 0
  for nv in g[i]:
    temp = max(temp, dfs(nv)+1)
  
  dp[i]=temp
  return temp
  
# finding overall longest path  
res = 0  
for i in range(n):
  res = max(res, dfs(i))
  
print(res)

Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())

g = [[] for i in range(n)]

for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)

# longest path from vertice i
def dfs(i):
  temp = 0
  for nv in g[i]:
    temp = max(temp,dfs(nv)+1)
  return temp

# iterate over all vertices

res = 0
for i in range(n):
  res = max(res, dfs(i))
  
print(res)

Fixed submission:
import sys

sys.setrecursionlimit(10**9)

n , m = map(int,input().split())

g = [[] for i in range(n)]

dp = [-1] *n
for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
  
# finding longest path for vertice i
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp = 0
  for nv in g[i]:
    temp = max(temp, dfs(nv)+1)
  
  dp[i]=temp
  return temp
  
# finding overall longest path  
res = 0  
for i in range(n):
  res = max(res, dfs(i))
  
print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))

ones , twos, threes = 0,0,0

for i in a:
  if i ==1:
    ones+=1
  elif i ==2:
    twos+=1
  else:
    threes+=1

max_ones = ones+twos+threes
max_twos = twos+threes
max_threes = threes
# dp[n][n][n]
dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

for k in range(max_threes+1):
  for j in range(max_twos+1-k):
    for i in range(max_ones+1-j-k):
      if i+j+k==0:
        continue
      else:
        dp[i][j][k] = n/i+j+k
        if i>0:
          dp[i][j][k] += (dp[i-1][j][k]*i)/(i+j+k)
        if j>0:
          dp[i][j][k] += (dp[i+1][j-1][k]*j)/(i+j+k)
        if k>0:
          dp[i][j][k] += (dp[i][j+1][k-1]*k)/(i+j+k)
          
          
print(dp[i][j][k])
        
        
        
        
        








Fixed submission:
n = int(input())
a = list(map(int,input().split()))

ones , twos, threes = 0,0,0

for i in a:
  if i ==1:
    ones+=1
  elif i ==2:
    twos+=1
  else:
    threes+=1

max_ones = ones+twos+threes
max_twos = twos+threes
max_threes = threes
# dp[n][n][n]
dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

for k in range(max_threes+1):
  for j in range(max_twos+1-k):
    for i in range(max_ones+1-j-k):
      if i+j+k==0:
        continue
      else:
        dp[i][j][k] = n/(i+j+k)
        if i>0:
          dp[i][j][k] += (dp[i-1][j][k]*i)/(i+j+k)
        if j>0:
          dp[i][j][k] += (dp[i+1][j-1][k]*j)/(i+j+k)
        if k>0:
          dp[i][j][k] += (dp[i][j+1][k-1]*k)/(i+j+k)
          
          
print(dp[i][j][k])
Buggy python submission (verdict: Runtime Error):
n = int(raw_input())

mat = []
for i in range(n):
    mat.append(map(int,raw_input().split()))
    
dp = [0,0,0]

for day in range(n):
    ndp = [0,0,0]
    data = mat[day]
    
    for i in range(n):
        for j in range(n):
            if i != j:
                ndp[j] = max(ndp[j], dp[i]+data[j])
    dp = ndp
print max(dp)
   

Fixed submission:
n = int(raw_input())

dp = [0]*(3)

for i in range(n):
    dp_new = [0]*3
    c=map(int,raw_input().split())
    
    for i in range(3):
        for j in range(3):
            if i != j:
                dp_new[j] = max(dp_new[j],dp[i]+c[j])
    dp = dp_new
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
times, jump = [int(i) for i in input().split()]
line = input()
list1 = []
if times <= 1:
  print("%s" % 0)
else: 
  for i in line.split():
    if i:
      list1.append(int(i))
  mem = [0] * times
  mem[-2] = abs(list1[-1] - list1[-2])
  for i in range(len(list1)-3, -1, -1):
    ans = float("inf")
    end = min(len(list1), i+jump+1)
    for k in range(i+1, end):
      ans = min(ans, abs(list1[i] - list1[k]) + mem[k])
    mem[i] = ans
  print("%s" % mem[0])


Fixed submission:
times, jump = [int(i) for i in input().split()]
line = input()
list1 = []
if times <= 1:
  print("%s" % 0)
else: 
  for i in line.split():
    if i:
      list1.append(int(i))
  mem = [0] * times
  mem[-2] = abs(list1[-1] - list1[-2])
  for i in range(len(list1)-3, -1, -1):
    ans = float("inf")
    end = min(len(list1), i+jump+1)
    for k in range(i+1, end):
      ans = min(ans, abs(list1[i] - list1[k]) + mem[k])
    mem[i] = ans
  print("%s" % mem[0])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = [int(i) for i in input().split()]
dp = [0 for i in range(W+1)] # dp[i] is the the max value you have achieve with weight i
for i in range(N):
  w,value = [int(i) for i in input().split()]
  for weight in range(W-w, -1, -1): # range of kanpsack weight in which i can push the current item
    dp[weight + w] = max(dp[weight + w], dp[weight] + value)
print("%s" % dp[W])


Fixed submission:
N, W = [int(i) for i in input().split()]
weight = []
value = []
for i in range(N):
  w, val = [int(i) for i in input().split()]
  weight.append(w)
  value.append(val)
# changing to value max as W_max ~ 10^9 and val_max ~= 1000 * next
val_max = 0
for i in range(N):
  val_max += value[i]
dp = [float('inf') for i in range(val_max+1)] # dp[i] is the min weight required for the value 
# hence our ans would be in the max value where the weight < knapsack weight
dp[0] = 0
for i in range(N):
  for v in range(val_max-value[i], -1, -1): # range of kanpsack weight in which i can push the current item
    dp[v + value[i]] = min(dp[v + value[i]], dp[v] + weight[i])
    #print(dp)
sol = 0
for i in range(val_max+1):
  if dp[i] <= W:
    sol = i
print("%s" % sol)

Buggy python submission (verdict: Runtime Error):
N,W = [int(i) for i in input().split()]
w = [] # limit weight to knapsack capacity
v = [] # maximize value
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
mem = [[0]*(W+1) for i in range(N)]
for i in range(w[0], W+1):
  mem[0][i] = v[0]
for i in range(1, N):
  for j in range(1, W+1):
    if w[i] > j:
      mem[i][j] = mem[i-1][j]
    else:
      mem[i][j] = max(mem[i-1][j], v[i] + mem[i-1][j - w[i]])
#print(mem)
print("%s" % mem[N-1][W])



Fixed submission:
N, W = [int(i) for i in input().split()]
weight = []
value = []
for i in range(N):
  w, val = [int(i) for i in input().split()]
  weight.append(w)
  value.append(val)
# changing to value max as W_max ~ 10^9 and val_max ~= 1000 * next
val_max = 0
for i in range(N):
  val_max += value[i]
dp = [float('inf') for i in range(val_max+1)] # dp[i] is the min weight required for the value 
# hence our ans would be in the max value where the weight < knapsack weight
dp[0] = 0
for i in range(N):
  for v in range(val_max-value[i], -1, -1): # range of kanpsack weight in which i can push the current item
    dp[v + value[i]] = min(dp[v + value[i]], dp[v] + weight[i])
    #print(dp)
sol = 0
for i in range(val_max+1):
  if dp[i] <= W:
    sol = i
print("%s" % sol)