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):
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    W, V = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[float('inf')]*(10**5+10) for i in range(N+1)]
    
    
    dp[0][0] = 0

    for i in range(N):
        for v in range(10**5+10):
            if v - V[i] >= 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v - V[i]] + W[i])
            dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    ans = 0
    for v in range(10**5 + 10):
        if dp[N][v] <= M:
            ans = v
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, W = list(map(int, input().split()))
    V = 100000
    INF = float('inf')
    dp = [[INF] * (V + 1) for _ 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(V + 1):
            if v > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j])
    ans = V
    while dp[n][ans] > W:
        ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

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

w=[0]*N
v=[0]*N

dp=[[10**20]*(10**5+1) for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    ww,vv=input().split()
    w[i]=int(ww)
    v[i]=int(vv)

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

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

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

Solution (Python):
def main():
    N, W = map(int, input().split())
    
    dp = [10**9+1 for _ in range(10**5+1)]
    for _ in range(N):
        w,v = map(int, input().split())
        for val in range(10**5, 1, -1):
            if val - v < 1:
                break
            dp[val] = min(dp[val], dp[val - v] + w)
        if dp[v] > w:
            dp[v] = w
    ans = 0
    for v, w in enumerate(dp):
        if w <= W:
            ans = max(ans, v)
    print(ans)
if __name__ == '__main__':
    main()

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

dp=[[10**11+1 for i in range(100*10**3+1)] for j in range(N+1)]

dp[0][0]=0

for i in range(1,N+1):
    for j in range(100*10**3+1):
        dp[i][j]=dp[i-1][j]
        if j - wv[i][1] >= 0:
            dp[i][j]=min(dp[i][j],dp[i-1][j-wv[i][1]]+wv[i][0])

            
res=0
for i in range(100*10**3+1):
    if dp[N][i]<=W:
        res=i
            
print(res)

Solution (Python):


from collections import deque

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(MAX_V):
        if j-_v < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-_v]+_w)

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

Solution (Python):
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    V = sum(value)
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V + 1):
            if v - value[i] >= 0:
                dp[i + 1][v] = dp[i][v - value[i]] + weight[i]
            if dp[i + 1][v] > dp[i][v]:
                dp[i + 1][v] = dp[i][v]

    ans = 0
    for v in range(V, 0, -1):
        if dp[N][v] <= W:
            ans = v
            break

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    V = sum(value)
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V + 1):
            if v - value[i] >= 0:
                dp[i + 1][v] = dp[i][v - value[i]] + weight[i]
            else:
                dp[i + 1][v] = weight[i]
            if dp[i + 1][v] > dp[i][v]:
                dp[i + 1][v] = dp[i][v]

    ans = 0
    for v in range(V + 1):
        if dp[N][v] <= W:
            ans = v
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    V = sum(value)
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V + 1):
            if v - value[i] >= 0:
                dp[i + 1][v] = dp[i][v - value[i]] + weight[i]
            if dp[i + 1][v] > dp[i][v]:
                dp[i + 1][v] = dp[i][v]

    ans = 0
    for v in range(V + 1):
        if dp[N][v] <= W:
            ans = v
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(ans)

Solution (Python):




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

W = []
V = []

for i in range(N):
    w,v = map(int,input().split())
    W.append(w)
    V.append(v)

import math
import numpy as np
dp = np.ones((10**3*(N+10))) * np.inf
dp[0] = 0
for v,w in zip(V,W):
    np.minimum(dp[:-v]+w, dp[v:],out=dp[v:])
print(np.where(dp<=W_max)[0][-1])

Solution (Python):




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

W = []
V = []

for i in range(N):
    w,v = map(int,input().split())
    W.append(w)
    V.append(v)

import math
import numpy as np
dp = np.ones((10**3*(N+10))) * np.inf
dp[0] = 0
for v,w in zip(V,W):
    np.minimum(dp[:-v]+w, dp[v:],out=dp[v:])
print(np.where(dp<=W_max)[0][-1])

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)






from bisect import bisect_left,bisect_right

n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

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

for i in range(1,n+1):
    for j in range(1,max_v+1):
        if j-V[i]>=0:
            dp[i][j]=min(dp[i-1][j-V[i]]+W[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]


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

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [10**12+1]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


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

Solution (Python):

l=input().split()
n=int(l[0])
W=int(l[1])
lweight=[]
lvalue=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	lweight.append(u)
	lvalue.append(v)
k=sum(lvalue)
dp=[[-1 for i in range(k+1)] for i in range(n+1)]
for i in range(n+1):
	dp[i][0]=0
for i in range(1,n+1):
	for j in range(1,k+1):
		if(dp[i-1][j]>-1):
			dp[i][j]=dp[i-1][j]
			if(j>=lvalue[i-1] and dp[i-1][j-lvalue[i-1]]!=-1):
				dp[i][j]=min(dp[i][j],dp[i-1][j-lvalue[i-1]]+lweight[i-1])
		elif(j>=lvalue[i-1] and dp[i-1][j-lvalue[i-1]]!=-1):
			dp[i][j]=dp[i-1][j-lvalue[i-1]]+lweight[i-1]
		else:
			dp[i][j]=-1
maxa=0
for i in range(n+1):
	for j in range(k+1):
		if(dp[i][j]!=-1 and dp[i][j]<=W):
			if(j>maxa):
				maxa=j
print(maxa)

Solution (Python):
import numpy as np
N,W = map(int,input().split())
V = 1000 * N + 1
dp = np.full(V,W + 1)
dp[0] = 0
for i 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())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())

V = sum(v)
dp = [[10**100]* (V + 1) for _ in range(N+1)]

dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        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])
        

ans = 0
for j in range(V + 1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Solution (Python):
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(100001)] for j in range(n+1)]
for i in range(1,100001):
    dp[0][i]=10**10
dp[0][0]=0    
for a in range(1,n+1):
    for b in range(1,100001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Solution (Python):
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(100001)] for j in range(n+1)]
for i in range(1,100001):
    dp[0][i]=10**10
dp[0][0]=0    
for a in range(1,n+1):
    for b in range(0,100001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Solution (Python):
N,W = map(int,input().split())
wv = []
a = 0
for i in range(N):
    w,v = map(int,input().split())
    a = max(v,a)
    wv.append((w,v))
A = N*a
inf = 10**15
dp = [[inf]*(A+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for v in range(A+1):
        if v-wv[i-1][1]>=0:
            dp[i][v] = min(dp[i-1][v-wv[i-1][1]]+wv[i-1][0],dp[i-1][v])

        else:
            dp[i][v] = dp[i-1][v]

ans = 0

for j in reversed(range(A+1)):
    if dp[N][j]<=W:
        ans = j
        break
print(ans)

Solution (Python):
N,W = map(int,input().split())
import numpy as np
dp = np.full(N*1000 +1,W+1,dtype=np.int64)
dp[0]=0
for _ 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())
box = []
v = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
  v.append(V)
vmax = n*max(v)
inf = float('inf')
dp = [[inf for i in range(vmax+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  for j in range(vmax+1):
    if j >= box[i-1][1]:
      dp[i][j] = min(dp[i-1][j-box[i-1][1]] + box[i-1][0],dp[i-1][j])
    else:
      dp[i][j] = min(dp[i][j],dp[i-1][j])
ans = []
for i in range(vmax+1):
  if dp[n][i] <= w:
    ans.append(i)
print(max(ans))

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, W = map(int, input().split())
    dp = [INF] * (n * 1001 + 1)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for v0 in range(n * 1001, -1, -1):
            if dp[v0] == INF:
                continue
            if v + v0 <= n * 1001:
                dp[v + v0] = min(dp[v + v0], dp[v0] + w)
    for v in range(n * 1001, -1, -1):
        if dp[v] <= W:
            print(v)
            return
resolve()

Solution (Python):
import numpy
N, W = map(int, input().split())
memo = numpy.array([[10**9+1 for i in range(10**5+1)] for j in range(N)])
memo[-1][0] = 0
for n in range(N):
    w, v = map(int, input().split())
    memo[n][:v] = memo[n-1][:v]
    memo[n][v:] = numpy.fmin(memo[n-1][v:], memo[n-1][:-v]+w)
a = numpy.where(memo[-1] <= W)
print(numpy.max(a[0]))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def resolve():
    return 

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range (N)]
INF = 10**10
VMAX = N * 10**3 + 10
dp = [[INF]*(VMAX) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(VMAX):
        if j>=wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = 0
for i in range(VMAX):
    if dp[N][i]<=W:
        ans = max(ans, i)

print(ans)

Solution (Python):
n, w = map(int, input().split())
V, W = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
max_sumv = sum(V) 

dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0
for i in range(n):
    for sum_v in range(max_sumv + 1):
        
        if sum_v - V[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - V[i]] + W[i])
        
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Solution (Python):
N, W = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
DP=[[float("inf")]*(N*10**3+1) for i in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    for j in range(N*10**3+1):
        if j-X[i-1][1] >= 0:
            DP[i][j]=min(DP[i-1][j], DP[i-1][j-X[i-1][1]]+X[i-1][0])
        else:
            DP[i][j] = DP[i-1][j]
ans = 0
for i in range(N+1):
    for j in range(N*10**3+1):
        if DP[i][j] <= W:
            ans = max(ans, j)
print(ans)

Solution (Python):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(V+1):
        if j-v>=0 and dp[i-1][j-v]+w<=W:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = 10**5
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
for k in range(V+1)[::-1]:
    if dp[-1][k]<=W:
        print(k)
        break

Solution (Python):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = LI()
    for j in range(V+1):
        if j-v>=0:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Solution (Python):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(V+1):
        if j-v>=0:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
ans = 0
for k in range(V+1):
    if dp[-1][k]<=W:
        ans = max(ans,k)
print(ans)

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

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

for i in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])
MAX_V = 10**5+100
INF = 10**10
dp = [[INF]*MAX_V for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_V):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(MAX_V):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, W = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]
    
    max_value = 1
    for i in range(n):
        max_value += goods[i][1]

    dp = [[f_inf for _ in range(max_value)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0

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

    res = 0
    for k in range(max_value):
        if dp[-1][k] <= W:
            res = k

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, W = map(int, input().split())
    goods = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1])
    max_value = 1
    for i in range(n):
        max_value += goods[i][1]

    dp = [[f_inf for _ in range(max_value)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0

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

    res = 0
    for k in range(max_value):
        if dp[-1][k] <= W:
            res = k

    print(res)


if __name__ == '__main__':
    resolve()

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())

V = sum(v)
dp = [[10**100]* (V + 1) for _ in range(N+1)]


dp[0][0] = 0
for i in range(N):
    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+1][j], dp[i][j])

ans = 0
for j in range(V + 1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Solution (Python):
import numpy as np

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

dp = [float("INF")]*(N*10**3 + 1)
dp = np.array(dp)
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())

dp = [[float('inf')]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0

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

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

Solution (Python):
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    
    
    
    
    V = N*max(v)
    INF = float('inf')
    dp = [[INF]*(V+1) for i in range(N)]
    for x in range(V+1):
        dp[0][x] = INF if x>v[0] else w[0]
    dp[0][0] = 0
    for i in range(N-1):
        for j in range(V+1):
            if j>=v[i+1]:
                
                dp[i+1][j] = min(dp[i+1][j], (dp[i][j-v[i+1]])+w[i+1])
            
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    
    for val in range(V,-1,-1):
        if dp[-1][val]<=W:
            print(val)
            break
main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    

    
    N, W = map(int, input().split())
    
    
    S = tuple(tuple(map(int, input().split())) for i in range(N)) 
    vmax=N*1000
    inf=10**10
    dp=[inf]*(vmax+1)
    dp[0]=0
    for i in range(N):
        w,v=S[i]
        j=vmax
        while j-v>=0:
            dp[j]=min(dp[j-v]+w,dp[j])
            j-=1
    ans=0
    for i, val in enumerate(dp):
        if val<=W:
            ans=i
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(n)]
inf = 10 ** 10
dp = [[inf] * (1000 * n + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(1000 * n + 1):
        if dp[i][j] == inf:continue
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

        w, v = wv[i]
        if dp[i][j] + w <= W:
            dp[i + 1][j + v] = min(dp[i + 1][j + v], dp[i][j] + w)

for i in range(1000 * n + 1):
    if dp[-1][-(i + 1)] != inf:
        print(1000 * n - i)
        exit()

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

N, W = map(int, input().split())
dp = [[10**18]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(10**5+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        
        if j+v<=10**5:
            dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j]+w)

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

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [0]+[inp[i][0] for i in range(N)]
v = [0]+[inp[i][1] for i in range(N)]
dp = FILL2(INF,N+1,100001)
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(100001):
        if j-v[i] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for j in range(100001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Solution (Python):
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n, W = rli()
	items = []
	maxval = 0
	for _ in range(n):
		w, v = rli()
		maxval += v
		items.append((w, v))

	dp = [INF for _ in range(maxval + 1)]
	dp[0] = 0
	for w, v in items:
		for i in range(maxval, -1, -1):
			if i - v >= 0:
				dp[i] = min(dp[i], dp[i-v] + w)
	ans = NINF
	for val, minweight in enumerate(dp):
		if minweight <= W:
			ans = val
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
n,W=map(int,input().split())
sumv=0
v,w=[],[]
m=10**9
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    sumv+=b
dp=[m]*(sumv+1)
dp[0]=0
for i in range(n):
    for j in range(sumv,v[i]-1,-1):
        dp[j]=min(dp[j],dp[j-v[i]]+w[i])
ans=0

for i in range(sumv+1):
    if dp[i]<=W:
        ans=i 

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
N,W= map(int,input().split())
ans= [[float('inf') for e in range(10**5+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for j in range(0,v):
  ans[i+1][j]=min(ans[i][j],w)
 for j in range(v,10**5+1):
  ans[i+1][j]=min(ans[i][j],ans[i][j-v]+w)
print(bisect.bisect(ans[N],W))

Solution (Python):
import sys

n,c = list(map(int, input().split()))
W=[]
P=[]
for _ in range(n):
    w,val = list(map(int, input().split()))
    W.append(w)
    P.append(val)
maxV = sum(P)
dp=[]
for i in range(n+1):
    dp.append([sys.maxsize]*(maxV+1))
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    for j in range(1,maxV+1):
        inc=sys.maxsize
        exc=sys.maxsize
        if j-P[i-1]>=0:
            inc=W[i-1]+dp[i-1][j-P[i-1]]
        exc=dp[i-1][j]
        dp[i][j]=min(inc,exc)
ans=0
for i in range(1,maxV+1):
    if dp[n][i]<=c:
        ans=i
print(ans)

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

dp = np.full(N*10**3+1,Max_W+1,dtype=np.int64)
dp[0] = 0
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-v] + w
    b = dp[v:]
    m = np.minimum(a,b)
    dp[v:] = m
max_w = 0
max_v = 0
ans = np.where( dp <= Max_W )
print(np.max(ans))

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




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



for i in range(1,N+1):
  for j in range(max(v_list)*N+1):
    
    if j - v_list[i-1] >= 0:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v_list[i-1]] + w_list[i-1])
    else:
      dp[i][j] = dp[i-1][j]
  


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

print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  dp=[[inf]*100100 for _ in range(n+1)]
  dp[0][0]=0

  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n):
    for j in range(100100):
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])

      if j+v[i]<100100:
        dp[i+1][j+v[i]]=min(dp[i+1][j+v[i]],dp[i][j]+w[i])

  ans=0
  for i in range(100100):
    x=dp[n][i]
    if x<=W:
      ans=i

  return ans


print(main())