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
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)








N, W = [int(x) for x in input().split()]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0

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

    add = defaultdict(lambda: float('inf'))
    for vv in list(dp.keys()):
        if dp[vv + v] > dp[vv] + w:
            add[vv + v] = dp[vv] + w
    dp.update(add)

print('hoge', file=sys.stderr)

print(max(filter(lambda i: i[1] <= W, dp.items()), key=lambda x:x[0])[0])

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)






N, W = [int(x) for x in input().split()]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0

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

    add = defaultdict(lambda: float('inf'))
    for vv in list(dp.keys()):
        if dp[vv + v] > dp[vv] + w:
            add[vv + v] = dp[vv] + w
    dp.update(add)

print(max(filter(lambda i: i[1] <= W, dp.items()), key=lambda x:x[0])[0])

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)






N, W = [int(x) for x in input().split()]

dp = [float('inf')] * 1000 * 100*10
vs = set()
vs.add(0)
dp[0] = 0

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

    tmpDP = dp.copy()
    for vv in list(vs):
        if dp[vv + v] > dp[vv] + w:
            tmpDP[vv + v] = dp[vv] + w
            vs.add(vv + v)
    dp = tmpDP


ans = 0
for v in list(vs):
    if dp[v] <= W:
        ans = max(ans, v)
print(ans)

Solution (Python):
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = map(int, input().split())
    weight.append(w_tmp)
    value.append(v_tmp)

INF = float('inf')

dp = [[INF for i in range(sum(value)+1)] for j in range(N+1)]
dp[0][0] = 0

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

for j in range(sum(value)+1):
    if dp[N][j] <= W:
        res = j

print(res)

Solution (Python):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for x in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]


dp = [[None] * (sum(vs) + 1) for _ in range(N + 1)]





















dp[-1] = [float("inf")] * len(dp[-1])
s = sum(vs)
for depth in range(N):
    for value in range(s + 1):
        if value - vs[depth] >= 0:
            dp[depth][value] = min(dp[depth - 1][value], dp[depth - 1][value - vs[depth]] + ws[depth])
        else:
            dp[depth][value] = min(dp[depth - 1][value], ws[depth])


import bisect
print(bisect.bisect_left(dp[N - 1], W + 1))

Solution (Python):
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in 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 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]
 
ans = 0
for j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)

Solution (Python):
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in 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 v[i] <= j:
      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 sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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 = (10 ** 3) * N + 5
Inf = 10 ** 18
dp = [[Inf] * V for _ in range(N)]


    
dp[0][0] = 0
dp[0][v[0]] = w[0]

for i in range(1, N):
    for j in range(V):
        if j >= v[i]:
            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(V):
    if dp[N - 1][j] <= W and j > ans:
        ans = j

print(ans)

Solution (Python):

N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

MAX_N = 110
MAX_V = 100100


dp = [[10**15 for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(MAX_V):
        
        if sum_v - Value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - Value[i]] + Weight[i])

        
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0

for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Solution (Python):

N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

MAX_N = 110
MAX_V = 100100
dp = [[10**15 for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0

for i in range(N):
    
    for sum_v in range(MAX_V):
        
        if sum_v - Value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - Value[i]] + Weight[i])

        
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


ans = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Solution (Python):
INF = float('inf')
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
V = 1000*N
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-wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j-wv[i][1]]+wv[i][0],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

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

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

max_value = 10**5+10
INF = 10**9+1
dp = [[INF for _ in range(max_value)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(max_value):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i][j-value[i]]+weight[i], dp[i][j])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]) 

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

print(ans)

Solution (Python):
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,W=LI()
INL = [tuple(LI()) for i in range(N)]
DP=[[10**18]*100001 for _ in range(N+1)]
DP[0][0] = 0

for i, (w, v) in enumerate(INL, 1):
    
    for j in range(100001):
        DP[i][j] = min(DP[i-1][j], DP[i][j])
        if (j+v) <= 100000:
            DP[i][j+v] = min(DP[i-1][j+v], DP[i-1][j]+w)

res = 0
for v, w in enumerate(DP[N]):
    if w <= W:
        res = max(res, v)


print(res)

Solution (Python):

N,W = map(int,input().split())
max_v = 1000
wv_l= []
for i in range(N):
    wv_l.append(list(map(int,input().split())))
DP = [[10**10]*(max_v*N +1) for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    for sum_v in range(max_v*N +1):


        if sum_v-wv_l[i][1] >= 0:
            DP[i+1][sum_v] = min(DP[i+1][sum_v],DP[i][sum_v-wv_l[i][1]] + wv_l[i][0])
        DP[i+1][sum_v] = min(DP[i+1][sum_v],DP[i][sum_v])


ans = -1
for i in range(len(DP[N])):
    if DP[N][i] <= W:
        ans = max(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())
V=sum(v)

dp=[[float('inf')]*(V+1) for i 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]=dp[i][j-v[i]]+w[i]
		dp[i+1][j]=min(dp[i+1][j],dp[i][j])
res=0
for i in range(V+1):
	if dp[N][i]<=W:res=max(i,res)
print(res)

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

INF = 10 ** 12
MAX_V = 10 ** 5 + 10
dp = [INF] * MAX_V
dp[0] = 0

for w, v in WV:
	for i in range(MAX_V - 1, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)
	

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

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

w=[]
v=[]

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

dp=[[float('inf')]*(V+1) for i in range(N+1)]
dp[0][0]=0
res=0
for i in range(N):
	for j in range(V+1):
		if j-v[i]>=0:
			dp[i+1][j]=w[i]+dp[i][j-v[i]]
		dp[i+1][j]=min(dp[i][j],dp[i+1][j])


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

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
vm=n*1000+1
dp=[[0]+[10**18]*vm]+[[0]*vm for _ in range(n)]
for i in range(1,n+1):
    w,v=g[i]
    for j in range(vm):
        k=j-v
        if k<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][k]+w)
for j in range(vm)[::-1]:
    if dp[n][j]<=W:
        print(j)
        break
"""))

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

inf = float("inf")

max_v = 1000 * N + 1
dp = [inf for _ in range(max_v)]
dp[0] = 0
sum_v = 0

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

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

Solution (Python):


import sys
def input():
    return sys.stdin.readline()[:-1]

N, W = map(int, input().split())
w, v = [], []
for i in range(1, N+1):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

V = sum(v)

dp = [[float("inf")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
"""
i番目を選ぶ場合
dp[i][j] = dp[i-1][j-v] + w
i番目を選ばない場合
dp[i][j] = dp[i-1][j]
"""

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


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

Solution (Python):
import sys
input = sys.stdin.readline
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())

n = (N+1)*max(v)

inf = 10**14

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

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

ans = 0
for i in range(n):
    if dp[N][i] <= W:
        ans = i
    else:
        break

print(ans)

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

for i in range(n):
    for j in range(10 ** 5 + 1):
        if 0 <= j - goods[i][1]:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - goods[i][1]] + goods[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])


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

Solution (Python):
N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

v_max=sum([x[1] for x in items])

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

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



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

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
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 i 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]=dp[i][j-v[i]]+w[i]
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])

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

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 i 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]=dp[i][j-v[i]]+w[i]
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])

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

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

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] = 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') for i in range(V+1)] for j 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]=dp[i][j-v[i]]+w[i]
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])

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

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

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] = 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):
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)]
"""
for j in range(V + 1):
	dp[0][j] = 0
"""
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):
def main():
    N, W = map(int, input().split())
    MV = 10**5
    dp = [float('INF')] * (MV + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(MV, -1, -1):
            if v > i:
                tmp = w
            else:
                tmp = dp[i - v] + w
            dp[i] = min(dp[i], tmp)
    ans = 0
    for v, w in enumerate(dp):
        if W >= w:
            ans = max(ans, v)
        else:
            break
    print(ans)


main()

Solution (Python):
def main():
    N, W = map(int, input().split())
    Ws = []
    Vs = []
    for _ in range(N):
        w, v = map(int, input().split())
        Ws.append(w)
        Vs.append(v)
    mv = sum(Vs)
    dp = [[float('INF')] * (mv + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(mv + 1):
            if Vs[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - Vs[i]] + Ws[i])
    for j in range(mv, -1, -1):
        if W >= dp[N][j]:
            print(j)
            break


main()

Solution (Python):
def main():
    N, W = map(int, input().split())
    Ws = []
    Vs = []
    for _ in range(N):
        w, v = map(int, input().split())
        Ws.append(w)
        Vs.append(v)
    mv = sum(Vs)
    dp = [[float('INF')] * (mv + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(mv + 1):
            if Vs[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - Vs[i]] + Ws[i])
    ans = 0
    for r in dp:
        for v, w in enumerate(r):
            if W >= w:
                ans = max(ans, v)
    print(ans)


main()

Solution (Python):
n,W=map(int, input().split())
a=[]
max_v=0
for _ in range(n):
    w,v=map(int, input().split())
    a.append((w,v))
    max_v+=v

dp=[[float('inf') for j in range(max_v+1)] for i in range(n+1)] 

for i in range(1,n+1):
    w,v=a.pop()
    for j in range(max_v+1):
        if j-v>=0:
            dp[i][j]=min(
                dp[i-1][j-v]+w 
                ,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    dp[i][v]=min(w,dp[i-1][v])
    
ans=0
for j in range(max_v+1):
    if dp[n][j]<=W:
        ans=j
print(ans)

Solution (Python):
N, W = map(int, input().split())
wv = [[int(_) for _ in input().split()] for _ in range(N)]
V_MAX = 10**5+1
dp = [[float('inf')]*(V_MAX) for _ in range(N+1)]
dp[0][0] = 0

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

for i in range(V_MAX):
    if dp[N][i] > W:
        print(i-1)
        break
else:
    print(i)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


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

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(N * 1000 + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= (j - cv) and (dp[i][j - cv] + cw) <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - cv] +  cw)

    return max([cv for cv, cw in enumerate(dp[-1]) if isfinite(cw)])


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))
    result = solve(N, W, w, v)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
items = []
INF = 10**12
for _ in range(N):
    items.append(tuple(map(int, input().split())))
MAX_V = sum([v for _, v in items])
dp = [[INF for j in range(MAX_V+1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(MAX_V+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j-v] + w, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
for v in range(MAX_V, -1, -1):
    if dp[N][v] <= W:
        break
print(v)

Solution (Python):
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
v_max = sum([i[1] for i in items])
INF = 10**12
dp = np.array([[INF for j in range(v_max+1)] for _ in range(N+1)])
dp[0, 0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.minimum(dp[i-1, :-v] + w, dp[i-1, v:])
ans = 0
for v in range(v_max, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

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

INF = 10 ** 12
V = 10 ** 3 * 100 + 10

dp = [0] + [INF] * V
for w, v in WV:
	for i in range(V, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)

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

"""
for cell in dp:
	if cell == INF:
		print("  INF", end="")
	else:
		print("{:5d}".format(cell), end="")
print()
"""

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


INF = 10 ** 12 
V = 10 ** 5 + 10

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

for i, (w, v) in enumerate(WV):
	for n in range(V):
		if v <= n:
			dp[i + 1][n] = min(dp[i + 1][n], dp[i][n - v] + w)
		dp[i + 1][n] = min(dp[i + 1][n], dp[i][n])
"""
for line in dp:
	for cell in line:
		if cell == INF:
			print("  INF", end="")
		else:
			print("{:5d}".format(cell), end="")
	print()
"""
r = 0
for i in range(V):
	if dp[-1][i] <= W:
		r = i
print(r)

Solution (Python):
import fileinput


def knapsack(capacity, item_weights, item_values):
    val_limit = sum(item_values) + 1

    prev_vals = [sum(item_weights)] * val_limit
    weight_table = [prev_vals]

    for item_id, item_value in enumerate(item_values):
        current_vals = [0] * val_limit
        for total_val in range(1, val_limit):
            if item_value >= val_limit - total_val:
                current_vals[total_val] = prev_vals[total_val]
            else:
                current_vals[total_val] = min(
                    prev_vals[total_val],
                    prev_vals[total_val + item_value] - item_weights[item_id]
                )

        prev_vals = current_vals
        weight_table.append(prev_vals)

    for val in range(0, val_limit)[::-1]:
        for item in range(1, len(item_weights) + 1):
            if weight_table[item][val] <= capacity:
                return val
    return 0


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))

Solution (Python):

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

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

total_v = sum(v)


INF = float('inf')
dp = [[INF] * (total_v + 1) for i in range(n + 1)]
dp[0][0] = 0

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

for j in range(total_v, -1, -1):
    if dp[n][j] <= max_w:
        ans = j
        break

print(ans)

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    w_,v_=map(int,input().split())
    w.append(w_)
    v.append(v_)
INF=10**9+1
dp=[[INF]*(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]>=0:
            dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i+1][j])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for j in range(10**5,-1,-1):
    if dp[N][j]<=W:
        ans=j
        break
print(ans)

Solution (Python):
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [10**12]*(1+10**5)
dp[0] = 0
for i in range(N):
    w,v = WV[i]
    for j in range(len(dp)-1, 0, -1):
        if j-v<=0:
            tmp = w
        else:
            tmp = dp[j-v] + w
        dp[j] = min(dp[j], tmp)
ans = 0
for v,w in enumerate(dp):
    if w<=W:
        ans = max(ans, v)
    else:
        break
print(ans)

Solution (Python):
import sys
from collections import defaultdict

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

inf = 10**14

dp = defaultdict(lambda : inf)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for dv, dw in dp.copy().items():
        if w + dw <= W:
            dp[dv + v] = min(dp[dv + v], w + dw)
print(max(dp.keys()))

Solution (Python):
import numpy as np

N = W = 0
g = []
MAX_V = 100100


def get_input():
    global N, W, g
    N, W = map(int, input().split())
    g = []
    for _ in range(N):
        g.append([int(x) for x in input().split()])


def dpcalc():
    global N, W, g
    
    dp = np.full((N + 1, MAX_V + 1), 10 ** 11)
    

    
    r = 1
    for i in range(1, N + 1):
        w, v = g[i - 1]
        dp[i][:v + 1] = np.minimum(dp[i - 1][:v + 1], w)
        dp[i][v + 1:v + r] = np.minimum(dp[i - 1][1: r] + w, dp[i - 1][v + 1:v + r] )
        
        r += v
        
    for i in range(MAX_V, -1, -1):
        if dp[N][i] <= W:
            return i
    return 0


get_input()
print(dpcalc())

Solution (Python):


n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] 
V=10**5
MAX=10**12
dp = [MAX]*(V+1)
dp[0]=0
newdp = [MAX]*(V+1)
for i in range(n):
    w, v = wv[i]
    newdp = dp[:]
    for j in range(V+1):
        if j+v <= V:
            newdp[j+v] = min(dp[j] + w, newdp[j+v])
    newdp, dp = dp, newdp


print(max([i for i,c in enumerate(dp) if c <= W]))

Solution (Python):


n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] 
V=10**5
MAX=10**12
dp = [MAX]*(V+1)
dp[0]=0
newdp = [MAX]*(V+1)
for i in range(n):
    w, v = wv[i]
    for j in range(V+1):
        newdp[j] = dp[j]
    for j in range(V+1):
        if j+v <= V:
            newdp[j+v] = min(dp[j] + w, newdp[j+v])
    newdp, dp = dp, newdp


print(max([i for i,c in enumerate(dp) if c <= W]))

Solution (Python):

"""
E - Knapsack 2
https://atcoder.jp/contests/dp/tasks/dp_e

"""
import sys


def solve(N, W, items):
    limit = 0
    for w, v in items:
        limit += v
    dp = [float('inf')] * (limit+1)
    dp[0] = 0
    for w, v in items:
        for i in range(limit, -1, -1):
            if dp[i] != float('inf') and dp[i]+w <= W:
                dp[i+v] = min(dp[i+v], dp[i]+w)

    ans = [i for i, d in enumerate(dp) if d != float('inf')]
    return max(ans)


def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

Vmax=sum(V)




dp = []
for _ in range(N):
	dp.append([None]*(Vmax+1))

dp[0][0] = 0
dp[0][V[0]] = W[0]

for i in range(1,N):
	
	
	
	
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			if dp[i-1][v] is not None:
				if dp[i-1][v-V[i]] is not None:
					dp[i][v] = min(dp[i-1][v],dp[i-1][v-V[i]]+W[i])
				else:
					dp[i][v] = dp[i-1][v]
			else:
				if dp[i-1][v-V[i]] is not None:
					dp[i][v] = dp[i-1][v-V[i]]+W[i]

ans = 0
for v in range(Vmax+1):
	try:
		ans = v if dp[-1][v]<=Wmax else ans
	except TypeError:
		pass

print(ans)

Solution (Python):
def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    v = [wv[i][1] for i in range(len(wv))]
    V = sum(v)
    dp = [[10 ** 9] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(V + 1):
            if j - wv[i][1] >= 0:
                dp[i + 1][j] = min(dp[i + 1][j],
                                   dp[i][j - wv[i][1]] + wv[i][0])
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
    for k, p in enumerate(dp[-1]):
        if p <= W:
            r = k
    return r


if __name__ == '__main__':
    ans = e()
    print(ans)

Solution (Python):
dp1=[None]*100001
dp2=[None]*100001
dp1[0]=0
dp2[0]=0
n,W=map(int,input().split())
for i in range(n):
    w,v=map(int,input().split())
    for i in range(v,100001):
        if(dp2[i-v]!=None):
            if(dp2[i]==None):
                dp1[i]=dp2[i-v]+w
            else:
                dp1[i]=min(dp2[i],dp2[i-v]+w)
    dp2=list(dp1)
for i in range(100000,-1,-1):
    if(dp2[i]!=None and dp2[i]<=W):
        print(i)
        break

Solution (Python):
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    V = sum(vv)
    INF = 10**12
    dp_table = [[INF for _ in range(V+1)] for _ in range(N+1)]
    dp_table[0][0] = 0
    for i in range(N):
        for j in range(V):
            v_next = vv[i] + j
            w_next = ww[i]
            d = dp_table[i][j]
            if v_next <= V:
                dp_table[i+1][v_next] = min(dp_table[i+1][v_next], d + w_next)
            dp_table[i+1][j] = min(dp_table[i+1][j], d)
    
    
    
    idxx = [i for i, w in enumerate(dp_table[-1]) if w <= W]
    print(idxx[-1])
sub()