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_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007
inf = 10**12


def main():
	
	n, max_w = IN()
	
	dp_v = [inf] * (10**5 + 100)
	dp_v[0] = 0
	for _ in range(n):
		add_v = []
		w, v = IN()
		for i, cv in enumerate(dp_v):
			if dp_v[i] == inf:
				continue
			if dp_v[i] + w < dp_v[i+v]:
				add_v.append((i+v, dp_v[i] + w))
		for i, nv in add_v:
			dp_v[i] = nv
			
	for i, min_w in enumerate(dp_v[::-1]):
		if min_w <= max_w:
			v=len(dp_v)-i-1
			return v
		
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
N,W = map(int,input().split())
weight = [0]
value = [0]
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
    
maxValue = sum(value)
INF = 10**10
dp = [[INF for i in range(maxValue+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    for v in range(1,maxValue+1):
        if value[i] <= v:
            dp[i][v] = min(dp[i-1][v],weight[i] + dp[i-1][v-value[i]])
        else:
            dp[i][v] = dp[i-1][v]
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Solution (Python):
N, W = map(int, input().split())
Weight = [0]
Value = [0]
ans = 0
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
VS = sum(Value)
DP = [[float('inf')] * (VS + 1) for i in range(N + 1)]

for n in range(N + 1):
    for val in range(VS + 1):
        if val == 0:
            DP[n][val] = 0
        elif Value[n] > val:
            DP[n][val] = DP[n - 1][val]
        else:
            DP[n][val] = min(DP[n - 1][val], DP[n - 1][val - Value[n]] + Weight[n])
            if (n == N) and (DP[n][val] <= W):
                ans = max(ans, val)

print(ans)

Solution (Python):






import numpy as np


N, W = map(int, input().strip().split())
t = []
for i in range(N):
    t.append(list(map(int, input().strip().split())))
table = np.array(t)


Vmax = N * max(table[:, 1])
dp = np.full(Vmax + 1, 10 ** 9)
dp[0] = 0


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


for j in range(Vmax, 0, -1):
    if dp[j] <= W:
        print(j)
        break

Solution (Python):
[n,w] = [int(i) for i in input().split()]
wv = []
for i in range(n):
    wv.append([int(i) for i in input().split()])
num = 100001

dp = [[10 ** 13]* num for i in range(n)]

"""
dp[i][j] = 重さ
i : i品目まで見たときの値
j : 価値の総和がjになる
"""
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    if i != 0:
        for j in range(num):
            if j >= wv[i][1]:
                dp[i][j] = min(dp[i][j],dp[i-1][j])
                dp[i][j] = min(dp[i][j],dp[i-1][j-wv[i][1]]+wv[i][0])
            else:
                dp[i][j] = min(dp[i][j],dp[i-1][j])
    else:
        dp[i][wv[i][1]] = wv[i][0]
ans = 0
for i in range(num):
    if dp[n-1][i] <= w:
        ans = i
print(ans)

"""
6 15
______
6 5
5 6
6 4
6 6
3 5
7 2

 0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,

[0, 100, 100, 100, 100,   6, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100, 100,   6,   5, 100, 100, 100, 100,  11, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100,   6, 100, 100, 100, 100,  12,  11, 100, 100, 100, 100,  17, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100,   6, 100,   6, 100, 100, 100,  12, 100, 100, 100, 100,  18,  17, 100, 100, 100, 100,  23, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100,   6,   3, 100, 100, 100,   9, 100,   9, 100, 100, 100,  15, 100, 100, 100, 100,  21,  20, 100, 100, 100, 100,  26, 100, 100, 100],
[0, 100,   7, 100, 100, 100,  13,  10, 100, 100, 100,  16, 100,  16, 100, 100, 100,  22, 100, 100, 100, 100,  28,  27, 100, 100, 100, 100,  33, 100]
]
"""

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, W = map(int, input().split())
    weights = []
    values = []
    for i in range(N):
        w, v = map(int, input().split())
        weights.append(w)
        values.append(v)
    V = max(values)
    dp = [[float("inf")] * (N * V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        w = weights[i]
        v = values[i]
        for j in range(N * V + 1):
            if j >= v:
                dp[i + 1][j] = min(dp[i][j - v] + w, dp[i][j])
            else:
                dp[i + 1][j] = dp[i][j]
    for j in range(N * V):
        if dp[-1][-j - 1] <= W:
            print(N * V - j)
            return


if __name__ == "__main__":
    main()

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

n, w = map(int, input().split())
v = 100*10**3
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [float("inf")]*v] + [[float("inf")]*(v+1) for _ in range(n)]
wei, val = 0, 1

for i in range(n):
    for j in range(v+1):
        if item[i][val] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j-item[i][val]] + item[i][wei])
        else:
            dp[i+1][j] = dp[i][j]

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

Solution (Python):
n, w = map(int, input().split())
goods = [list(map(int, input().split())) for _ in range(n)]
dp = [[10 ** 11] * (10 ** 5 + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    weight, value = goods[i]
    for sum_value in range(10 ** 5 + 1):
        if (sum_value - value) >= 0:
            dp[i + 1][sum_value] = min(dp[i + 1][sum_value], dp[i][sum_value - value] + weight)
        dp[i + 1][sum_value] = min(dp[i + 1][sum_value], dp[i][sum_value])

ans = 0
for sum_value in range(10 ** 5 + 1):
    if dp[n][sum_value] <= w:
        ans = sum_value

print(ans)

Solution (Python):
import sys
INF = 10**18
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N,W = LI()
dp = [INF for _ in range(N*1000+1)]

dp[0] = 0
for i in range(N):
    w,v = LI()
    for j in range(len(dp)-1,0,-1):
        if j-v < 0: continue
        dp[j] = min(dp[j],dp[j-v]+w)

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

Solution (Python):
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]
import numpy as np
V=N*1000+1
dp=np.ones(V,dtype=np.int64)*(W+1)
dp[0]=0
for w,v in WV:
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
print(max([i for i in range(V) if dp[i]<=W]))

Solution (Python):
n,w = map(int, input().split())
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

INF = 1 << 30

dp = [[INF for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)

Solution (Python):
n,w = map(int, input().split())
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

dp = [[float("inf") for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)

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

VMAX = 1000
INF = 1 << 30
dp = [[INF] * (N * VMAX + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
	for j in range(N * VMAX + 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])

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

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    total_value = sum(v)
    dp = [[float("inf")] * (total_value + 1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

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

    weight = 0
    res = 0
    for j in range(total_value+1):
        if dp[-1][j] <= W:
            weight = dp[-1][j]
            res = j
    print(res)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Solution (Python):
n, w = map(int, input().split())
ws, vs = [], []
for _ in range(n):
    wi, vi = map(int, input().split())
    ws.append(wi)
    vs.append(vi)
sum_v = sum(vs)
dp = [float('inf')] * (sum_v + 1)
dp[0] = 0
for i in range(n):
    for j in range(sum_v - vs[i], -1, -1):
        dp[j + vs[i]] = min(dp[j] + ws[i], dp[j + vs[i]])
ans = 0
for vi, wi in enumerate(dp):
    if wi <= w:
        ans = vi
print(ans)

Solution (Python):
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 = sum(v)

dp = [[float("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 - 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):
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 = sum(v)

dp = [[float("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 - 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())
pairs = list(tuple(map(int, input().split())) for _ in range(N))
v_sum = sum(v for _, v in pairs)

dp = np.full((N+1, v_sum+1), W * 2, dtype = np.int64)
dp[0][0] = 0

for (i, (w, v)) in enumerate(pairs):
    dp[i+1] = dp[i]
    dp[i+1, v:] = np.minimum(dp[i+1, v:], dp[i, :v_sum-v+1] + w)

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

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * (N * (10 ** 3) + 1)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
  
for i,count in enumerate(dp):
    if dp[i] <= W:
        ans = i
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * N * (10 ** 4)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
  
for i,count in enumerate(dp):
    if dp[i] <= W:
        ans = i
print(ans)

Solution (Python):
import numpy as np
 
N, W = map(int, input().split())
WV = np.array([input().split() for _ in range(N)], np.int64)
V = sum(WV[:,1])
dp = np.zeros(V + 1, np.int64)
dp += 10 ** 10
dp[0] = 0
for w, v in WV:
    dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
for v in range(V + 1):
    if dp[v] <= W:
        ans = v
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n, k = inpl()
max_value = 10 ** 5 + 1

dp = [[INF] * max_value for i in range(n + 1)]
dp[0][0]=0
for i in range(n):
    w, v = inpl()
    for j in range(max_value):
        include = dp[i][j-v] + w if j-v>=0 else INF
        not_include = dp[i][j]
        dp[i + 1][j] = min(include, not_include)
tmp = dp[n][:]
for i in range(max_value-1, -1, -1):
    if tmp[i] <=k:
        print(i)
        break

Solution (Python):
import numpy as np

N, W = map(int, input().split())
WV = np.array([input().split() for _ in range(N)], np.int64)
V = sum(WV[:,1])
dp = np.zeros(V + 1, np.int64)
dp += 10 ** 10
dp[0] = 0
for w, v in WV:
    dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
for v in range(V + 1):
    if dp[v] <= W:
        ans = v
print(ans)

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

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

dp = [10**10]*(10**5)
dp = np.array(dp)

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


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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
WV = np.array([input().split() for _ in range(N)], np.int64)
V = sum(WV[:, 1])
INF = 1 << 60
dp = np.full(V + 1, INF)
dp[0] = 0
for w, v in WV:
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])
for v in range(V + 1):
    if dp[v] <= W:
        ans = v
print(ans)

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

v = [0] * N
w = [0] * N
for i in range(N):
    w[i],v[i] = map(int,input().split())
sumv = sum(v)+1
dp = [[float('inf')] * (sumv) for _ in range(N+1)]
for i in range(N):
    dp[i][0] = 0
for i in range(1, N+1):
    for j in range(1, sumv):
        if v[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],w[i-1]+dp[i-1][j-v[i-1]])
ans = 0
for i in range(1, sumv+1):
    if dp[N][-i] <= W:
        ans = sumv - i
        break
print(ans)

Solution (Python):
n,wmax=map(int,input().split())
v=[0]*n
w=[0]*n
for i in range(n):
    w[i],v[i]=list(map(int,input().split()))
sv=sum(v)+1
dp=[[float('inf')]*sv for _ in range(n)]
dp[0][v[0]-1]=w[0]
for i in range(n):
    dp[i][0]=0
for i in range(n):
    for j in range(sv):
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
ans=float('inf')
for p in range(sv-1,-1,-1):
    if dp[n-1][p]<=wmax:
        ans=p
        break
print(ans)

Solution (Python):
n,wmax=map(int,input().split())
v=[0]*n
w=[0]*n
for i in range(n):
    w[i],v[i]=list(map(int,input().split()))
sv=sum(v)+1
dp=[[float('inf')]*sv for _ in range(n)]
dp[0][v[0]-1]=w[0]
for i in range(n):
    dp[i][0]=0
for i in range(n):
    for j in range(sv):
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
ans=float('inf')
for p in range(sv-1,-1,-1):
    if dp[n-1][p]!=ans and dp[n-1][p]<=wmax:
        ans=p
        break
print(ans)

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

INF = 10**10
dp = [INF]*(10**5+1)
dp[0] = 0
for w, v in wv:
    newdp = dp[:]
    for vv in range(10**5):
        if v+vv>10**5:
            break
        newdp[v+vv] = min(dp[v+vv], dp[vv]+w)
    dp = newdp
for v, w in enumerate(reversed(dp)):
    if w<=W:
        print(10**5-v)
        break

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

for i in range(n):
  a,b = map(int, input().split())
  x.append(b)
  y.append(a)

max_num = sum(x)

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

for i in range(n):
  for j in range(max_num + 1):
    if(j >= x[i]):
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - x[i]] + y[i])
    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
    
print(max(list(int(i) for i in range(max_num + 1) if dp[n][i] <= w)))

Solution (Python):
n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
M = sum(V) + 1

INF = 1 << 60
dp = list([INF] * M for _ in range(n + 1))
dp[0][0] = 0
for i in range(n):
    for v in range(M):
        if v >= V[i]:
            dp[i + 1][v] = min(dp[i][v], dp[i][v - V[i]] + W[i])
        else:
            dp[i + 1][v] = dp[i][v]
for v in range(M):
    if dp[n][v] <= max_weight:
        ans = v
print(ans)

Solution (Python):

def main():
    N, W = map(int, input().split())
    w = [None for _ in range(N)]
    v = [None for _ in range(N)]
    for i in range(N):
        w[i], v[i] = map(int, input().split())
    MAX_V = sum(v)
    dp = [[10**9 for _ in range(MAX_V+1)] for _ in range(N)]
    dp[0][0] = 0
    for i in range(N-1):
        if i == 0:
            for sum_v in range(1, v[i]+1):
                dp[i][sum_v] = w[i]
        for sum_v in range(MAX_V+1):
            if sum_v - v[i+1] >= 0:
                dp[i+1][sum_v] = min(w[i+1] + dp[i]
                                     [sum_v-v[i+1]], dp[i][sum_v])
            else:
                dp[i+1][sum_v] = min(w[i+1], dp[i][sum_v])
    print(len(list(filter(lambda sum_v: sum_v <= W, dp[-1])))-1)


if __name__ == "__main__":
    main()

Solution (Python):
N,W= map(int,input().split())
w=[]
v=[]
for  i 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) ]
for  i in range(N):
    dp[i][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][j] , dp[i][j-v[i]]+w[i])

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

print(ans)

Solution (Python):
INF = 10**13

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

dp = [[INF]*100010 for _ in range(N+1)]

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

for ans_v in range(100010):
    if dp[N][ans_v] > W:
        ans = ans_v
        break
print(ans)

Solution (Python):
N,W=map(int,input().split())
k=[[0,0] for i in range(N)]
dp=[[W+1]*(1001*101+1) for j in range(N+1)]
R=set()
for i in range(N):
    k[i][0],k[i][1]=map(int,input().split())

dp[0][0]=0
for i in range(0,N):
    for v in range(1001*101):
        if v - k[i][1]>=0:
            dp[i+1][v] = min(dp[i][v-k[i][1]]+k[i][0],dp[i][v])
        else:
            dp[i+1][v]=min(dp[i+1][v],dp[i][v])

        if dp[i][v]<W:
             R.add(v)


for v in reversed(range(1001*101+1)):
    if dp[N][v]<=W:
        print(v)
        exit()

Solution (Python):
N,W=map(int,input().split())
k=[[0,0] for i in range(N)]
dp=[[W+1]*(1001*101+1) for j in range(N+1)]
R=set()
for i in range(N):
    k[i][0],k[i][1]=map(int,input().split())
dp[0][:k[0][1]]=[k[0][0]]*(k[0][1]+1)
dp[0][0]=0
for i in range(1,N):
    for v in range(1001*101):
        if v - k[i][1]>=0:
         dp[i][v] = min(dp[i-1][v-k[i][1]]+k[i][0],dp[i-1][v])
        else:
            dp[i][v]=min(dp[i-1][v],dp[i][v])

        if dp[i][v]<W:
             R.add(v)


for v in reversed(range(1001*101+1)):
    if dp[N-1][v]<=W:
        print(v)
        exit()

Solution (Python):

def main():
    import sys, copy
    N, W = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    
    
    dp =[[10**11+1 for _ in range(10**5+1)] for _ in range(N)]
    dp[0][L[0][1]] = L[0][0] 
    
    for i in range(1, N):
        
        dp[i] = copy.copy(dp[i-1]) 
        w, v = L[i][0], L[i][1]
        
        
        dp[i][v] = min(w, dp[i][v])
        
        for j in range(10**5+1-v):
            if dp[i-1][j] !=0:
                dp[i][v+j] = min(dp[i][v+j], w + dp[i-1][j])
    
    
    
    ans = 0
    for v1,w1 in enumerate(dp[-1]):
        if w1 <= W:
            if ans < v1:
                ans = v1
            
    print(ans)

if __name__ =='__main__':
    main()

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = INF * np.ones(vsum + 1, dtype=int)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        w, v = things[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])
    return np.where(dp <= W)[0][-1]


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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = [INF] * (vsum + 1)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        dn = list(dp)
        w, v = things[i]
        for j in range(vsum - v + 1):
            w2 = dp[j] + w
            if j + v <= vsum and w2 <= W:
                dn[j + v] = min(dn[j + v], w2)
        dp = dn
    for i in range(vsum, -1, -1):
        w = dp[i]
        if w <= W:
            return i
    return 0  


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

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")


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



initW = 10**9+1

vmax = 1000*100


dp = [[initW for v in range(vmax+1)] for _r in range(N+1)]

dp[0][0] = 0	


for iN in range(1,N+1):
	for iV in range(vmax+1):
		w,v = WV[iN]
		
		w0 =      dp[iN-1][iV]
		w1 = (w + dp[iN-1][iV-v]) if (iV-v >= 0) else initW
	
		dp[iN][iV] = min(w0, w1)

ans=0

for iV in range(vmax+1):
	w = dp[N][iV]
	if w>W: continue
	ans = max(ans,iV)

print(ans)

Solution (Python):
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())




sum_v = sum(v)
dp = [[float("inf")]*(sum_v+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(sum_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(sum_v+1):
    if dp[n][j] <= W:
        ans = j
print(ans)

Solution (Python):


N, W = list(map(int, input().split()))
W_l = []
V_l = []
for i in range(N):
    w, v = list(map(int, input().split()))
    W_l.append(w)
    V_l.append(v)

V_max = sum(V_l)+1
W_max = sum(W_l) +1


dp = [[W+1] * V_max for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    
    for v in range(V_max):
        if v -V_l[i] >= 0:
            dp[i+1][v] = min(dp[i][v-V_l[i]]+W_l[i], dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]
    
ans = 0

for v, w in enumerate(dp[-1]):
    if w <= W and ans <= v:
        ans = v
print(ans)

Solution (Python):
N,W = list(map(int,input().split()))
WV = []
Vsum = 0
for i in range(N):
    [Wtmp,Vtmp] = list(map(int,input().split()))
    WV.append([Wtmp,Vtmp])
    Vsum += Vtmp

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

W0 = WV[0][0]
V0 = WV[0][1]

for j in range(Vsum+1):
    if V0>=j:
        dp[0][j] = W0

for i in range(1,N):
    newW = WV[i][0]
    dp[i][0] = min(newW,dp[i-1][0])

for i in range(1,N):
    newW = WV[i][0]
    newV = WV[i][1]
    for j in range(1,Vsum+1):
        if j<=newV:
            dp[i][j] = newW
        if j-newV>=0:
            dp[i][j] = min(dp[i-1][j-newV]+newW,dp[i][j])
        dp[i][j] = min(dp[i-1][j],dp[i][j])

out = 0
for i in range(N):
    for j in range(Vsum+1):
        if dp[i][j]<=W:
            if j >= out:
                out = j

print(out)

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())
max_v = max(v)



dp = [[10**18]*(n*max_v+1) for i in range(n)]

for i in range(n) :
    dp[i][0] = 0

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

for j in range(n*max_v,-1,-1) :
    if dp[n-1][j] <= W :
        print(j)
        break

Solution (Python):

class obj:
    def __init__(self,w,v):
        self.w = w
        self.v = v
        self.r = v/w

x = input().split()
N = int(x[0])
M = int(x[1])
item = []
item = []
for i in range(N):
    x = input().split()
    item.append(obj(int(x[0]),int(x[1])))

maxV = 0


def getKey(x):
    return x.r


item.sort(key=getKey, reverse=True)
	
def Bound(i, C):	
    global item, N
    
    sw = 0
    sv = 0
    j = i
    f = 1.0
    while j < N and f == 1.0:
        wj = min(C-sw, item[j].w)
        f = float(wj)/item[j].w
        sw += f*item[j].w
        sv += f*item[j].v
        j += 1
    return sv



def dfsv4(i, sumW, sumV):
    """prning bounding, branching"""
    global maxV, item, N, M
    if i == N:
        if sumW <= M:
            maxV = max(maxV, sumV)
    else:   
        temp1 = Bound(i+1, M-sumW) + sumV
        temp2 = Bound(i,M-sumW) + sumV
        is1 = False

        if temp1 > temp2:
            is1 = True

        if is1:
            if temp1 > maxV:
                dfsv4(i+1, sumW, sumV)
            if sumW + item[i].w <= M:
                if temp2 > maxV:
                    dfsv4(i+1, sumW+item[i].w, sumV+item[i].v)
        else:
            if sumW + item[i].w <= M:
                if temp2 > maxV:
                    dfsv4(i+1, sumW+item[i].w, sumV+item[i].v)
            if temp1 > maxV:
                dfsv4(i+1, sumW, sumV)


dfsv4(0,0,0)

print(maxV)

Solution (Python):

import sys, io, os

BUFSIZE = 8192


class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    
    from collections import defaultdict as dd, deque
    def data():
        return sys.stdin.readline().strip()

    def mdata():
        return map(int, data().split())

    out = sys.stdout.write
    
    INF = int(10e9)

    def knapSack(V):
        for i in range(n + 1):
            for v in range(V + 1):
                if v == 0:
                    K[i][v] = 0
                elif val[i - 1] <= v:
                    K[i][v] = min(wt[i - 1] + K[i - 1][v - val[i - 1]], K[i - 1][v])
                else:
                    K[i][v] = K[i - 1][v]

        return K[n][V]

    n, w = mdata()
    val = [0] * (n)
    wt = [0] * (n)
    for i in range(n):
        wt[i], val[i] = mdata()
    V = 100005
    K = [[1000000007 for x in range(V + 1)] for x in range(n + 1)]
    knapSack(V)
    m = 0
    for i in range(n + 1):
        for v in range(V + 1):
            if 1 <= K[i][v] <= w:
                m = max(m, v)
    print(m)

if __name__ == '__main__':
    main()