Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as f
n,s=map(int,input().split())
k=f(int)
k[0]=0
g=0
for i in range(n):
    w,v=map(int,input().split())
    c=list(k)
    for i in range(len(c)-1,-1,-1):
        if c[k[i]+v]!=0:
            c[k[i]+v]=min(c[k[i]]+w,c[k[i]+v])
        else:
            c[k[i]+v]=c[k[i]]+w
        if c[k[i]+v]<=s:
            g=max(g,k[i]+v)
print(g)

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        if j < wv[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],  wv[i-1][1] + dp[i-1][j - wv[i-1][0]])
        
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
def main():
    N, W = [int(n) for n in input().split()]
    baggages = [[int(n) for n in input().split()] for i in range(N)]

    VALUE, WEIGHT = 1, 0
    dp = [[-1] * (W+1) for n in range(N)]
    # dp[baggage][weight] := baggage番目までの荷物を使ってweight以下に抑える
    dp[0] = [0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE] for weight in range(W+1)]

    for baggage in range(N):
        for max_weight in range(W+1):
            if dp[baggage][max_weight] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][max_weight]
            val2 = dp[baggage-1][max_weight-bag_w]+bag_v if max_weight >= bag_w else 0
            dp[baggage][max_weight] = max(val1, val2)
            
    print(dp[N-1][W])



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    
MAX_WEIGHT = 1000000009
dp = [[MAX_WEIGHT for i in range(max_total+1)] for j in range(N+1)]
dp[0][0]=0
i = 0
for w, v in p:
    i += 1
    for target_val in range(0, max_total+1):
        
        if target_val-v >=0 and dp[i-1][target_val] > (dp[i-1][target_val-v]+w):
            dp[i][target_val] = dp[i-1][target_val-v]+w
        else:
            dp[i][target_val] = dp[i-1][target_val]
            
ret = 0
for v, w in enumerate(dp[N]):
    if w<=W and v>ret:
        ret = v
print(ret)

Submission status: Runtime Error

Solution code:
import numpy as np
n,w=map(int,input().split())
a=np.zeros([n,w+1],dtype=int)
c,d=map(int,input().split())
a[0][c:]=d
for i in range(1,n):
    e,f=map(int,input().split())
    a[i][:e]=a[i-1][:e]
    a[i][e:]=np.maximum(a[i-1][e:],a[i-1][:-e]+f)
print(a[-1][-1])

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
import numpy as np 

N, W = map(int, input().split())
w_all = np.zeros(W + 1, dtype=int)

for i in range(N):
  w, v = map(int, input().split())
  w_all[w:] = np.maximum(w_all[w:], w_all[:-w] + v)

print(w_all[W])

Submission status: Runtime Error

Solution code:
import numpy as np
n, wt = map(int, input().split())
d = np.zeros(wt+1,'i8')

for i in range(n):
  w, v = map(int, input().split())
  d[w:] = np.maximum(d[w:], d[:-w]+v)
print(d[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/2
Update on 2019/3/5
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_A():  # Frog 1
    N = getInt()
    H = getIntList()
    dmp((N, H), 'N, H')
    c = zeros(N)
    c[1] = abs(H[1]-H[0])
    for i in range(2, N):
        c[i] = min(c[i-1] + abs(H[i]-H[i-1]),
                   c[i-2] + abs(H[i]-H[i-2]))
    dmp(c, 'c')
    return c[N-1]


def prob_B_TLE():  # Frog 2 3/16 TLE
    N, K = getIntList()
    H = getIntList()
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N)
    c[0] = 0
    for i in range(1, N):
        #c[i] = INF
        for j in range(max(0, i-K), i):
            c[i] = min(c[i], c[j] + abs(H[i]-H[j]))
    dmp(c, 'c')
    return c[N-1]


def prob_B():  # Frog 2
    N, K = getIntList()
    H = np.array(input().split(), dtype='int')
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N, dtype=np.longlong)
    c[0] = 0
    for i in range(1, N):
        c[i] = np.min(c[max(0, i-K):i] + np.abs(H[max(0, i-K):i] - H[i]))
    dmp(c, 'c')
    return c[N-1]


def prob_C():  # Vacation
    N = getInt()
    a = zeros(N)
    b = zeros(N)
    c = zeros(N)
    for i in range(N):
        a[i], b[i], c[i] = getIntList()
    dmp(N, 'N')
    dmp(a, 'a')
    dmp(b, 'b')
    dmp(c, 'c')
    dpa = zeros(N)
    dpb = zeros(N)
    dpc = zeros(N)
    dpa[0] = a[0]
    dpb[0] = b[0]
    dpc[0] = c[0]
    for i in range(1, N):
        dpa[i] += max(dpb[i-1], dpc[i-1]) + a[i]
        dpb[i] += max(dpc[i-1], dpa[i-1]) + b[i]
        dpc[i] += max(dpa[i-1], dpb[i-1]) + c[i]
    dmp(dpa, 'dpa')
    dmp(dpb, 'dpb')
    dmp(dpc, 'dpc')
    return max(dpa[N-1], dpb[N-1], dpc[N-1])


def prob_D():  # Knapsack 1
    N, W = getIntList()
    w, v = zeros(N), zeros(N)
    dmp((N, W))
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp(w, 'weight')
    dmp(v, 'value')
    dp = zeros(W+1)
    dmp(dp.size)
    for i in range(N):
        dmp(dp, 'dp')
        dmp(w[i], 'w[i]')
        dp[w[i]:] = np.maximum(dp[w[i]:],
                               dp[:W-w[i]+1] + v[i])
    dmp(dp, 'dp')
    return dp[W]


def prob_E():  # Knapsack 2
    N, W = getIntList()
    w, v = zeros(N), zeros(N)
    dmp((N, W))
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp(w, 'weight')
    dmp(v, 'value')
    dp = zeros(W+1)
    dmp(dp.size)
    for i in range(N):
        dmp(dp, 'dp')
        dmp(w[i], 'w[i]')
        dp[w[i]:] = np.maximum(dp[w[i]:],
                               dp[:W-w[i]+1] + v[i])
    dmp(dp, 'dp')
    return dp[W]


debug = False  # True False
ans = prob_E()
print(ans)
#for row in ans:
#    print(row)

Submission status: Runtime Error

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:total_v-v[i]+1]+w[i])
for i inrange(sum(v)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
import numpy as np

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

N = N_W[0]
W = N_W[1]

w = []
v = []

for i in range(N):
    w_v =  list(map(int,input().split()))
    w.append(w_v[0])
    v.append(w_v[1])

dp = np.zeros(W+1,int)

for w1,v1 in zip(w,v):

    dp[w1:] = np.maximum(dp[w1:],dp[:W-w1 + 1] + v1)

print(dp.max())

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]


def solve():
    dp = [[0]*(W+1) for _ in range(N+1)]

    # init
    # update
    for i in range(1, N+1):
        for w in range(W+1):
            if w-items[i-1][0] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1]
                               [w-items[i-1][0]]+items[i-1][1])
            else:
                dp[i][w] = dp[i-1][w]

    print(max(dp[N]))


def solve2():
    dp = [0]*(W+1)
    for i in range(N):
        for w in reversed(range(W+1)):  # revにしないと、更新済みの値を使って更新しちゃう
            if w-items[i][0] >= 0:
                dp[w] = max(dp[w], dp[w-items[i][0]]+items[i][1])
    print(dp[-1])


solve2()

Submission status: Runtime Error

Solution code:
# E
import numpy as np
n,w = map(int, input().split())
 
items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')
 
for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*num for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(num):
        if v + nap[i][1] <= num:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(num)):
    if dp[n][v] <= w:
        print(v)
        exit()

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(num) for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(num):
        if v + nap[i][1] <= num:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(num)):
    if dp[n][v] <= w:
        print(v)
        exit()

Submission status: Runtime Error

Solution code:
import numpy as np
IN() = lambda:map(int, input().split())

n,k = IN()
dp = np.full(n*1000+1, k+1, dtype=int)
dp[0] = 0

for _ in range(n):
  w,v = IN()
  dp[v:] = np.minimum(dp[:-v]+w, dp[v:])

print(np.max(np.where(dp <= k)))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
cf=sorted( [ [int(x) for x in input().split()] for _ in range(N) ] )
dp = [0]*(W+1)
cnt=0
for w, c in cf:
    cnt=cnt+w
    for i in range(min(cnt, W), w-1, -1):
        if dp[i]<dp[i-w]+c:
            dp[i]=dp[i-w]+c
        
print(max(dp))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv < dp[nv]:
                dp[nv] = nw
        else:
            dp[nv] = nw

print(max(dp.keys()))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                dp[nv] = nw
        else:
            dp[nv] = nw
            
print(max(dp.key()))

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [0] * (W+1)
# i 円以下で買える商品の最大価値
for i in range(N):
    for weight in range(W,-1,-1):
        if weight - w[i] < 0 :continue
        DP[weight] = max(DP[weight], DP[weight - w[i]] +v[i])
print(DP[-1])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
ws = []
vs = []
for _ in range(n):
    w_, v_ = map(int, input().split())
    ws.append(w_)
    vs.append(v_)

base = min(ws)
dp = [[0]*(w+1-base-1) for _ in range(n+1)]

for n_ in range(1,n+1):
    temp_w = ws[n_-1]
    temp_v = vs[n_-1]
    #print(temp_w)
    for w_ in range(base, w+1-base):
        #print(w_)
        if temp_w <= w_+base:
            dp[n_][w_] = max(dp[n_-1][w_-temp_w]+temp_v, dp[n_-1][w_])
        else:
            dp[n_][w_] = dp[n_-1][w_]
print(dp)
#print(dp[n][w-base])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = []
for _ in range(n):
    wv.append(list(map(int, input().split())))

dp = [[0]*(w+1) for _ in range(n+1)]

for n_ in range(1,n+1):
    temp_w = wv[n_-1][0]
    temp_v = wv[n_-1][1]
    for w_ in range(1, w+1):
        if temp_w <= w_:
            dp[n_][w_] = max(dp[n_-1][w_-temp_w]+temp_v, dp[n_-1][w_])
        else:
            dp[n_][w_] = dp[n_-1][w_]
print(dp[n][w])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
X = [0] + [-1] * 110000
ma = 0
for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(len(X))[::-1]:
        if X[j] >= 0:
            if X[j] + w <= W:
                if j + v > 100000:
                    break
                if X[j+v] < 0:
                    # print(j+v, "->", X[j]+w)
                    X[j+v] = X[j]+w
                    ma = max(ma, j+v)
                else:
                    X[j+v] = min(X[j+w], X[j]+w)
                # print(X[:100])

print(ma)

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
X = [0] + [-1] * 110000
ma = 0
for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(len(X)-1, -1, -1):
        if X[j] >= 0:
            if X[j] + w <= W:
                if X[j+v] < 0:
                    # print(j+v, "->", X[j]+w)
                    X[j+v] = X[j]+w
                    ma = max(ma, j+v)
                else:
                    X[j+v] = min(X[j+w], X[j]+w)
                # print(X[:100])

print(ma)

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
X = [0] + [-1] * W

for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(W, -1, -1):
        if j + w > W:
            continue
        if X[j] >= 0:
            X[j+w] = max(X[j+w], X[j]+v)

print(max(X))

Submission status: Runtime Error

Solution code:
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())

items = [list(map(int, input().split())) for _ in range(N)]
v_sum = sum([item[1] for item in items])

inf = float("inf")
dp = [inf for _ in range(v_sum + 1)]

dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        if dp[j] >= dp[j - items[i][1] + items[i][0]]:
            dp[j] = dp[j - items[i][1]] + items[i][0]

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        exit()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())

items = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in items])

inf = float("inf")
dp = [inf for i in range(v_sum + 1)]

dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        if dp[j] > dp[j - items[i][1] + items[i][0]]:
            dp[j] = dp[j - items[i][1]] + items[i][0]

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        exit()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
dp = [[0] * (W + 1) for i in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
      if j - w >= 0:
        dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)
      else:
        dp[i+1][j] = dp[i][j]
print(max(dp[N]))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wl = [0]*(N+1)
vl = [0]*(N+1)
for i in range(1, N+1):
    wl[i], vl[i] = map(int, input().split())

MAX = W
dp = [0]*(MAX+1)

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1-w)):
        if k + w > MAX:
            break
        else:
            dp[k+w] = max(dp[k+w], dp[k] + v)
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecurisonlimit(10**9)
N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
rom bisect import bisect
def inpl(): return list(map(int, input().split()))

N, L = inpl()
DP = [1e9]*(10**5 + 2)
DP[0] = 0
for i in range(N):
    DP2 = [1e9]*(10**5 + 2)
    w, v = inpl()

    for i in range(10**5, v-1, -1):
        DP2[i] = min(DP[i-v] + w, DP[i], DP2[i+1])
    for i in range(v-1, -1, -1):
        DP2[i] = min(DP[i], DP2[i+1])
    DP = DP2
print(bisect(DP, L)-1)

Submission status: Runtime Error

Solution code:
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0
for w, v in Things:
    for nv, nw in list(dp.items()):
        if nw + w <= W:
            dp[nv + v] = min(dp[nv + v], nw + w)
ans = 0
for v, w in dp.items():
    if w <= W and v >= ans:
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))