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 .

Solution (Python):
def solve(items, n, W):
    V = sum([v for _, v in items])
    dp = [float('inf')] * (V + 1)
    dp[0] = 0

    for w, v in items:
        for i in range(V, v-1, -1):
            dp[i] = min(dp[i], dp[i-v] + w)
    
    for i in range(V, -1, -1):
        if dp[i] <= W:
            return i

    return 0


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print(solve(items, n, w))


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
N,W = map(int,input().split())
dp = [0]*(10**3+1)+[10**12]*(10**5)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(len(dp)-1,1000,-1):
        dp[j] = min(dp[j],dp[j-v]+w)
print(bisect.bisect_right(dp,W)-1001)

Solution (Python):
import numpy as np
N,W = map(int, input().split())

dp = np.full(N*1000+1, W+1, dtype=int)
dp[0] = 0

for _ in range(N):
  w,v = map(int, input().split())
  dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
  
print(np.max(np.where(dp<=W)))

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

import numpy as np
dp = np.full(N*1000+1, W+1, dtype=int)
dp[0] = 0


for _ in range(N):
  w,v = map(int, input().split())
  dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    MAX_V = 10 ** 3 * N + 1

    dp = [[W+1 for _ in range(MAX_V)] for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for mv in range(MAX_V):
        for i, (w, v) in enumerate(items):
            if mv - v >= 0:
                dp[i+1][mv] = min(dp[i][mv], dp[i][mv - v] + w)
            else:
                dp[i+1][mv] = dp[i][mv]

    print(max([v for v, w in enumerate(dp[N]) if w <= W]))

if __name__ == '__main__':
    main()

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

w = []
v = []

for i in range(N):
    a,b = list(map(int,input().split()))
    w.append(a)
    v.append(b)

DP = [[float('inf')]*(100001) for i in range(N+1)]

DP[0][0] = 0

for i in range(N):
    for j in range(100001):
        DP[i+1][j] = DP[i][j]
        if j >= v[i]:
            DP[i+1][j] = min(w[i]+DP[i][j-v[i]],DP[i+1][j])

for i in range(100001):
    if DP[N][100000-i] <= W:
        break
print(100000-i)

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

L = 100001
dp = [float('inf')]*100001
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    for k in reversed(range(v,L)):
        dp[k] = min(dp[k], dp[k-v]+w)

print(next(v for v,w in zip(reversed(range(L)), reversed(dp)) if w <= W))

Solution (Python):
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
V = sum([x[1] for x in goods])
INF = 10**10
dp = [[INF]*(V+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(V):
        if j+1 >= goods[i][1]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-goods[i][1]] + goods[i][0])
        else:
            dp[i+1][j+1]= dp[i][j+1]
ans = 0
for i in range(V):
    if dp[N][i+1] <= W:
        ans = i+1
print(ans)

Solution (Python):
from sys import stdin,stdout

print = stdout.write
input = stdin.readline
INF = 1e10
n,W = map(int,input().split())

wgt = [0]
val = [0]
for i in range(n):
    w,v = map(int,input().split())
    wgt.append(w)
    val.append(v)

max_val=sum(val)    
dp=[[INF for x in range(max_val+1)] for x in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    vi = val[i];wi = wgt[i]
    for V in range(1,max_val+1):
        if vi<= V:
            dp[i][V] = min(wi+dp[i-1][V-vi],dp[i-1][V])
        else:
            dp[i][V]=dp[i-1][V]
res = 0
for i in range(max_val,-1,-1):
    if dp[n][i] <= W:
        res = i
        break
print(str(res))

Solution (Python):


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

w,v=[0],[0]

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

dp=[[10**12 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i+1]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i+1]]+w[i+1],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]

ans=0

for sum_v in range(N*max(v)+1):
    if dp[N][sum_v]<=W:
        ans=max(ans,sum_v)
print(ans)

Solution (Python):


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

weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)



max_sum_v = N * 1000
inf = float("inf")
dp = [[inf for i in range(max_sum_v + 1)] for j in range(N + 1)]




dp[0][0] = 0




for i in range(N):
    for sum_v in range(max_sum_v + 1):
        if sum_v - value[i] >= 0:
            dp[i + 1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - value[i]] + weight[i])
        else:
            dp[i + 1][sum_v] = dp[i][sum_v]

for sum_v in range(max_sum_v + 1):
    if dp[N][sum_v] <= W:
        res = sum_v

print(res)

Solution (Python):
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+1):
        if j - V[i] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Solution (Python):
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

VMAX = 10**5 + 100
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf'):
            dp[n+1][v] = min(dp[n+1][v], dp[n][v])
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])

print(ans)

Solution (Python):

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())


import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

for i in range(N):
    dp[i+1, v[i]:] = np.minimum(dp[i, v[i]:], dp[i, :-v[i]]+w[i])
    dp[i+1, :v[i]] = dp[i, :v[i]]

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)

Solution (Python):
n,w=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)

Solution (Python):
import numpy as np

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



INF = 10**10
dp = np.array([INF] * 10**6)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    
    
    
    
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])


ans = 0
for i in range(len(dp)):
    if dp[i] <= W:
        ans = i
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

max_v = 0
dp = np.full(1000*N+1, 10**18, dtype=np.int64)
dp[0] = 0
for w, v in zip(w, v):
	np.minimum(dp[v:max_v+v+1], dp[:max_v+1]+w, out=dp[v:max_v+v+1])
	max_v += v
print(np.where(dp <= W)[0].max())

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

ans = 0
for i in range(len(dp)):
	if dp[i] <= W:
		ans = i
print(ans)

Solution (Python):
import numpy as np

N, W = map(int, input().split())
dp = np.array([W + 1] * (N * 1000 + 1))
dp[0] = 0
for _ in range(N):
  w, v = map(int, input().split())
  dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
max_value = 0
for v, w in enumerate(dp):
  if w <= W:
    max_value = v
print(max_value)

Solution (Python):

def knapsack_heavy(weight_limit: int, weights: list, values: list) -> int:
    max_value = sum(values)
    dp = [0] + [1 << 30] * max_value  
    for w, v in zip(weights, values):
        for cur_v in range(max_value, v - 1, -1):
            if dp[cur_v - v] + w < dp[cur_v]:
                dp[cur_v] = dp[cur_v - v] + w
    return max(v for v, w in enumerate(dp) if w <= weight_limit)


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict


def knapsack_heavy(limit: int, weight: list, value: list) -> int:
    dp = defaultdict(lambda: 1 << 30)  
    dp[0] = 0
    for w, v in zip(weight, value):
        for cur_v, cur_w in tuple(dp.items()):
            if w + cur_w <= limit:
                dp[v + cur_v] = min(dp[v + cur_v], w + cur_w)
    return max(dp.keys())


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Solution (Python):

def knapsack_heavy(limit: int, weight: list, value: list) -> int:
    lim = sum(value)
    dp = [0] + [1 << 30] * lim  
    for w, v in zip(weight, value):
        for cur_v in range(lim, v - 1, -1):
            dp[cur_v] = min(dp[cur_v], dp[cur_v - v] + w)
    ret = max(v for v, w in enumerate(dp) if w <= limit)
    return ret


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Solution (Python):
N, W = map(int, input().split())
max_v = 100 * 10**3
dp = [float("inf")] * (max_v + 1)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for dp_v in reversed(range(max_v+1)):
        dp_w = dp[dp_v]
        if (dp_v == 0 or dp_w < float("inf")) and dp_v + v <= max_v:
            dp[dp_v + v] = min(dp[dp_v + v], dp[dp_v] + w)

ans = 0
for v, w in enumerate(dp):
    if w <= W:
        ans = max(ans, v)

print(ans)

Solution (Python):
n, w = map(int, input().split())
dp = [[(10**9+1) for _ in range(10**5+1)] for _ in range(n)]
wn, vn = map(int, input().split())
dp[0][0] = 0
dp[0][vn] = wn
for i in range(1, n):
    wn, vn = map(int, input().split())
    for j in range(10**5+1):
        if (j - vn) >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-vn] + wn)
        else:
            dp[i][j] = dp[i-1][j]

ansl = dp[n-1][::-1]

for k in range(len(ansl)):
    if ansl[k] <= w:
        print(10**5-k)
        break

Solution (Python):
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,w = li()
l = []
for i in range(n):l.append(li())
l.sort()
d = defaultdict(int)
for i in range(10**5 + 10):d[i] = float('inf')
for i in l:

    for j in range(10 ** 5 + 10,0,-1):
        d[j + i[1]] = min(d[j + i[1]],d[j] + i[0])
    d[i[1]] = min(d[i[1]],i[0])
ans = 0
for i in range(10**5 + 10):
    if d[i] <= w:ans = i
print(ans)

Solution (Python):
n, w = map(int, input().split())
item_max = 100
val_max = 1000
col_max = item_max * val_max


dp = [[float('inf') for _ in range(col_max + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    wi, vi = map(int, input().split())
    for j in range(1, col_max + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j],
                            dp[i - 1][j - vi] + wi)
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(col_max + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Solution (Python):
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
d=full(10**6,W+1)
d[0]=0
exec("w,v=f();d[v:]=minimum(d[:-v]+w,d[v:]);"*N)
print(max(where(d<=W)[-1]))

Solution (Python):
import numpy as np
N,W=map(int,input().split())
dp=np.full(10**5+1,W+1)
dp[0]=0
for i in range(N):
    w,v=map(int,input().split())
    dp[v:]=np.minimum(dp[:-v]+w,dp[v:])
print(np.max(np.where(dp<=W)))

Solution (Python):


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

jwels=[]

for _ in range(N):
    jwels.append(list(map(int,input().split())))

dp=[10**10]*(10**5+1)
dp[0]=0

for w,v in jwels:
    for i in range(10**5+1)[::-1]:
        if dp[i]!=10**10 and i+v<=10**5:
            dp[i+v]=min(dp[i]+w,dp[i+v])



for i in range(10**5+1)[::-1]:
    if dp[i]<=W:
        print(i)
        break

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)
dp=[[float('inf')]*(V+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
    for sum_v in range(V+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][sum_v-v[i]]+w[i])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
res = 0
for i in range(V+1):
    if dp[N][i]<=W:
        res = i
print(res)

Solution (Python):
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)

for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]



sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = min(dp[i - 1][j], weight[i] + dp[i - 1][j - value[i]])
        else:
            dp[i][j] = dp[i -1][j]
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Solution (Python):
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)

for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]

sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = weight[i] + dp[i - 1][j - value[i]]
        
        dp[i][j] = min(dp[i][j], dp[i -1][j])
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Solution (Python):
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)

for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]

sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = min(dp[i][j], weight[i] + dp[i - 1][j - value[i]])
        
        dp[i][j] = min(dp[i][j], dp[i -1][j])
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

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

dp = []
valmax = int(1e5)
INF = int(1e10)
for _ in range(N+1):
    dp.append([INF] * (valmax+1))
dp[0][0] = 0

for i in range(N):
    for v in range(valmax+1):
        dp[i+1][v] = min(dp[i][v], dp[i][v - wv[i][1]] + wv[i][0])

maxval = 0
for k, l in enumerate(dp[N]):
    if l <= W:
        maxval = max(maxval, k)
    else:
        continue
print(maxval)

Solution (Python):
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N), [0] * (N)
for i in range(N):
    weight[i], value[i] = [int(i) for i in input().split()]



sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0



for i in range(N):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i + 1][j] = min(weight[i] + dp[i][j - value[i]], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])



ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i
        
print(ans)

Solution (Python):
n, w = map(int, input().split())
a = [[int(i) for i in input().split(" ")] for j in range(n)]
dp = [[0]+[float("inf")]*(10**5) for i in range(n+1)]
for i in range(1, n+1):
    w_, v_ = a[i-1]
    for j in range(1, 10**5+1):
        if j < v_:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j-v_]+w_, dp[i-1][j])
for i in range(10**5, -1, -1):
    if dp[n][i]<=w:
        print(i)
        break

Solution (Python):
n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
v_x = n*max(v)+1
dp = [[float("inf")]*(v_x) for x in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(v_x):
        if j < v[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])

res = 0
for i in range(v_x):
    if dp[n][i]<=wei:
        res = i
print(res)

Solution (Python):
from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs, INF=(10**11)+1):
    V = sum([v for w, v in pairs])
    dp = [[INF for j in range(V+1)] for i in range(N+1)]
    dp[0][V] = sum([w for w, v in pairs])
    for i, j in product(range(0, N), range(V, -1, -1)):
        w, v = pairs[i]
        dp[i+1][j] = dp[i][j]
        if 0 <= j + v <= V:
            dp[i+1][j] = min(dp[i][j], dp[i][j+v] - w)
    vmax = 0
    for j, i in product(range(V, -1, -1), range(0, N+1)):
        if dp[i][j] <= W:
            vmax = j
            break
    return vmax


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): 
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    MV = max(v)*N+1
    inf = float("inf")
    dp = [[inf]*MV for i in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(MV):
            if v[i] <= j:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j] = dp[i][j]
    ldp = dp[N]
    for i in reversed(range(MV)):
        if ldp[i] <= W:
            print(i)
            exit()

if __name__ == "__main__":
    main()

Solution (Python):
N,W=map(int,input().split())
oj=[]
for i in range(N):
  oj.append(list(map(int,input().split())))
M=100*1001
dp=[10**10]*M
dp[0]=0
for i in range(N):
  for j in range(M,-1,-1):
    if j+oj[i][1]<M:
      k=j+oj[i][1]
      dp[k]=min(dp[k],dp[j]+oj[i][0])
v=0
for i in range(M):
  if dp[i]<=W:v=i
print(v)

Solution (Python):
N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)


M = 100 * 1001
dp = [10**10] * M

dp[oj[0][1]] = oj[0][0]

for i in range(1,N):
    for j in range(M, -1, -1):
        if j + oj[i][1] < M:
            dp[j + oj[i][1]] = min(dp[j + oj[i][1]], dp[j] + oj[i][0])
    dp[oj[i][1]] = min(dp[oj[i][1]], oj[i][0])

v = 0
for i in range(M):
    if dp[i] <= W:
        v = i
print(v)

Solution (Python):

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

w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
    
INF = 1000000010
MAX_V = 100010 
dp = [[INF] * (MAX_V + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for value in range(MAX_V):
        if value >= v[i]:

            dp[i][value] = min(dp[i][value], dp[i - 1][value-v[i]] + w[i])

        dp[i][value] = min(dp[i-1][value], dp[i][value])
    
ans = 0
for i in range(MAX_V+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):
import bisect

N, W = map(int, input().split())
w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
INF = 1000000010
MAX_V = 100010
dp = [[INF] * MAX_V for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for value in range(MAX_V):
        if value <= v[i]:
            dp[i][value] = min(dp[i-1][value], w[i])
        else:
            dp[i][value] = min(dp[i - 1][value], dp[i-1][value-v[i]] + w[i])

print(bisect.bisect_right(dp[N], W)-1)

Solution (Python):
n, W = map(int, input().split())
w = []
v = []
for _ in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

dp = [[float('inf') for j in range(10**5+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(10**5+1):
        if j < v[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i])
ans = 0
for i in range(10**5,-1,-1):
    if dp[n][i] <= W:
        ans = i
        break
print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

def main():
    n, m = map(int, readline().split())
    inf = 10**11
    dp = [inf] * (1000 * n + 1)
    dp[0] = 0

    for i in range(n):
        w, v = map(int, input().split())
        for j in range(1000 * n - v, -1, -1):
            if dp[j] != inf:
                dp[j + v] = min(dp[j + v], dp[j] + w)
    ans = 0
    for a, b in enumerate(dp):
        if b <= m:
            ans = max(ans, a)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
inf = 10**11
dp = [inf] * (1000 * n + 1)
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    for j in range(1000 * n - v, -1, -1):
        if dp[j] != inf:
            dp[j + v] = min(dp[j + v], dp[j] + w)
ans = 0
for a, b in enumerate(dp):
    if b <= m:
        ans = max(ans, a)
print(ans)

Solution (Python):
MAX_N = 110
MAX_V = 100100
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
INF = float('inf')
dp = [[INF] * MAX_V for _ in range(MAX_N)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_V):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
res = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        res = sum_v
print(res)

Solution (Python):
N, W = list(map(int, input().split()))
INF = int(1e11)
dp = [[INF for i in range(int(1e5)+1)] for j in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    w, v = list(map(int, input().split()))
    for j in range(0, int(1e5)+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j], dp[i-1][j])

for j in reversed(range(int(1e5)+1)):
    for i in range(N+1):
        if dp[i][j] <= W:
            print(j)
            break
    else:
        continue
    break

Solution (Python):
N, W = list(map(int, input().split()))
INF = int(1e11)
dp = [[INF for i in range(int(1e5)+1)] for j in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    w, v = list(map(int, input().split()))
    for j in range(0, int(1e5)+1):
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

for j in reversed(range(int(1e5)+1)):
    for i in range(N+1):
        if dp[i][j] <= W:
            print(j)
            break
    else:
        continue
    break

Solution (Python):
import bisect
n,W=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
V=sum(v)
INF=10**10
G=[[INF]*(V+3) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(V+3):
    if j-v[i-1]<0:
      G[i][j]=min(G[i-1][j],w[i-1])
    else:
      G[i][j]=min(G[i-1][j],G[i-1][j-v[i-1]]+w[i-1])
A=G[n][0:V+3]
print(bisect.bisect_right(A,W,lo=0,hi=len(A)))

Solution (Python):
n, w = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for _ in range(n)]
v = sum(list(zip(*wv))[1])


dp = [[float("inf")] * (v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    w_i, v_i = wv[i]
    for j in range(v+1):
        
        if j - v_i >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v_i] + w_i)
        
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = 0
for j in range(v+1):
    if dp[n][j] <= w:
        ans = j

print(ans)

Solution (Python):
n, lim_w = map(int, input().split())
w, v = [], []

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


dp = [ [float("inf")]*(100005) for _ in range(n+1) ]
dp[0][0] = 0

for i in range(n):
    for j in range(100005):
        
        if j >= v[i]:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
        
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for v in range(100005):
    if dp[n][v] <= lim_w:
        ans = max(ans, v)

print(ans)

Solution (Python):
def main():
    goods, weight_limit = map(int, input().split())
    weight = []
    value = []
    for _ in range(goods):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    max_value = 10 ** 5 + 10
    dp = [[float("inf") for _ in range(max_value + 1)] for _ in range(goods + 1)]
    dp[0][0] = 0
    for i in range(goods):
        for v in range(max_value + 1):
            if v >= value[i]:
                dp[i + 1][v] = min(dp[i][v], dp[i][v - value[i]] + weight[i])
            else:
                dp[i + 1][v] = dp[i][v]
    answer = 0
    for i in range(max_value):
        if dp[-1][i] <= weight_limit:
            answer = max(answer, i)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
N,W = map(int,input().split())
ls = []
sum_v = 0
for i in range(N):
    ls.append(list(map(int,input().split())))
    sum_v += ls[-1][1]


dp = [[10**9+7]*(sum_v+1) for i in range(N+1) ]

dp[0][0] = 0

for i in range(1,N+1):
    w,v = ls[i-1]
    for j in range(0,sum_v+1):
        if j>=v:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v] + w)
            
            

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

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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

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

ans = np.where(dp[N] <= W)[0].max()

print(ans)

Solution (Python):















n, w = list(map(int, input().split()))
wl = [0] * n
vl = [0] * n
v = 100001
for i in range(n):
    wl[i], vl[i] = map(int, input().split())

INF = float("inf")
dp = [[INF]*(v+1)for _ in range(n+1)]  
dp[0][0] = 0
for i in range(n):
    for j in range(v+1):
        if j-vl[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-vl[i]]+wl[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Solution (Python):
N,W = map(int,input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int,input().split())

sumv = sum(v)
inf = float('inf')

dp = [[inf]*(sumv+1) for _ in range(N+1)]
for row in range(N+1):
    dp[row][0] = 0


for i in range(N):
    for j in range(sumv+1):
        dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i]) 




ans = 0
for i in range(N+1):
    for j in range(sumv+1):
        if dp[i][j] <= W: 
            ans = max(ans,j)
print(ans)