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):
INF=10**18
n,m=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
k=sum(v)
dp=[INF]*(k+1)
dp[0]=0
for i in range(n):
  for j in range(k,-1,-1):
    if j>=v[i] and dp[j-v[i]]!=INF:dp[j]=min(dp[j],dp[j-v[i]]+w[i])
for i,x in enumerate(dp):
  if x<=m:ans=i
print(ans)

Solution (Python):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
sum_v = sum(wv[i][1] for i in range(n))
sum_w = sum(wv[i][0] for i in range(n))

dp = [[sum_w + 1] * (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 - 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])

ans = 0
for j in range(sum_v + 1):
    if dp[n][j] <= w:
        ans = max(ans, j)
print(ans)

Solution (Python):
N,W = map(int,input().split())
w,v = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    w[i],v[i] = map(int,input().split())
SUM_V = sum(v)+1

INF = float('inf')
dp = [[INF for _ in range(SUM_V)] for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(SUM_V):
        
        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][sum_v],dp[i+1][sum_v])
res = 0



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

print(res)

Solution (Python):
def main():
    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())
    V = sum(value)
    dp = [[float('inf')] * (V + 5) for _ in range(N + 5)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V+1):
            if v - value[i] >= 0:
                dp[i+1][v] = min(dp[i][v-value[i]] + weight[i], dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    ans = 0
    for v in range(V+1):
        if dp[N][v] <= W:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n,p=map(int,input().split())
num=[list(map(int,input().split())) for _ in range(n)]
cnt=0
for i in range(n):
    cnt+=num[i][1]
dp=[[10**10]*(cnt+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    w=num[i-1][0]
    v=num[i-1][1]
    for j in range(cnt+1):
        dp[i][j]=dp[i-1][j]
    dp[i][v]=min(dp[i][v],w)
    for j in range(1,cnt+1-v):
        if dp[i-1][j]!=10 and dp[i-1][j]+w<=p:
            dp[i][j+v]=min(dp[i][j+v],dp[i-1][j]+w)
ans=0
for i in range(n+1):
    for j in range(1,cnt+1):
        if dp[i][j]<=p:
            ans=max(ans,j)
print(ans)

Solution (Python):





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

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

for w, v in wv:
    for i in range(10 ** 5, 0, -1):
        if i - v < 0:
            break

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

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

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

def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]

    sum_v = sum([value for weight, value in wv])
    dp = [w + 1] * (sum_v + 1)
    dp[0] = 0
    for weight, value in wv:
        for i in range(sum_v - value + 1)[::-1]:
            if dp[i + value] > dp[i] + weight:
                dp[i + value] = dp[i] + weight

    for i in range(sum_v + 1)[::-1]:
        if dp[i] <= w:
            print(i)
            break

main()

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

MAX = 10**11 + 1
dp = [[MAX]*(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(0, N*10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    
ans = 10**6 + 1
for k in range(N*10**3+1):
    if dp[N][k] <= W:
        ans = k

print(ans)

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():


    n, w = LI()
    weight = [0 for _ in range(n+1)]
    value = [0 for _ in range(n+1)]

    for i in range(1,n+1):
        weight[i], value[i] = LI()


    dp = [[float("inf") for _ in range(sum(value)+1)]  for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(len(dp[0])):
            if j < value[i+1]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-value[i+1]] + weight[i+1])

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

Solution (Python):
N,W = map(int,input().split())
l = [list(map(int,input().split())) for i in range(N)]
w,v = [list(i) for i in zip(*l)]
INF = 10**9+7
dp = [[INF] * (100001) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(100001):
        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]
ans = 100000
while dp[N][ans] > W:
    ans -= 1
print(ans)

Solution (Python):
N,W = map(int,input().split())
l = [list(map(int,input().split())) for i in range(N)]
w,v = [list(i) for i in zip(*l)]
INF = 10**9+7
dp = [[INF] * (100001) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(100001):
        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]
ans = 100000
while dp[N][ans] > W:
    ans -= 1
print(ans)

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

MAXV = 10**5+1
INF = 10**18
dp = [[INF]*(MAXV+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    w, v = WV[i]
    for j in range(MAXV+1):
        dp[i+1][j] = dp[i][j]
    for j in range(MAXV+1):
        if j+v <= MAXV:
            dp[i+1][j+v] = min(dp[i][j]+w, dp[i+1][j+v])
ans = 0
for i in range(n+1):
    for j in range(MAXV+1):
        temp = dp[i][j]
        if temp <= W:
            ans = max(j, ans)
print(ans)

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


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

for i in range(1, n+1):
    for j in range(sum(v) + 1):
        dp[i][j] = dp[i-1][j]
        if j - v[i] >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + w[i])
ans = 0
for i in range(sum(v)+1):
    if dp[n][i] <= W:
        ans = max(ans, i)

print(ans)

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


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5




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



dp[0][0] = 0

w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)


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

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


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5




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



dp[0][0] = 0

w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)


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

Solution (Python):

def main():
    import numpy as np

    N, W = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    v_max = 10 ** 3 * 100 * 10
    w_max = 10 ** 9 * v_max

    
    dp = np.full(v_max, w_max, dtype=np.int64)
    
    dp[0] = 0

    for w, v in lst:
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

    print(np.asarray(dp <= W).nonzero()[0].max())


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import numpy as np

    np.set_printoptions(linewidth=200)

    N, W = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    v_max = 10 ** 3 * 100 * 10
    w_max = 10 ** 9 * v_max

    
    dp = np.full(v_max, w_max, dtype=np.int64)
    
    dp[0] = 0

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

    ans = 0
    for i, w in enumerate(dp):
        if w <= W:
            ans = i
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
INF = float('inf')
N, W = map(int, input().split())


dp = [[INF] * 100010 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(100010):
        if j >= v:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

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

print(ans)

Solution (Python):
INF = float('inf')

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


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

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

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

print(ans)

Solution (Python):
n, w = map(int, input().split())
knap = [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 j - knap[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j-knap[i][1]] + knap[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]
for i in range(10**5, 0, -1):
    if dp[n][i] <= w :
        print(i)
        exit()

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_)
dp=[[float('inf')]*(100001) for i in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  for j in range(100001):
    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]
  
ans=100000
while dp[n][ans]>W:
  ans-=1
print(ans)

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

import numpy as np

dp = np.full(10 ** 5 + 1, 10 ** 10, dtype = int)
dp[0] = 0

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

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

Solution (Python):

import sys
input = sys.stdin.readline

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

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

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

print(ans)

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


def main(n,w,p):
    
    dp = [[0 for i in range(n*10**3+1)]]
    ans = 0
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(n*10**3+1):
            
            cur = 0
            if j<item[1]:
                cur = dp[i][j]
                temp.append(cur)
            elif j==item[1]:
                cur = item[0]
                if dp[i][j]:
                    cur = min(item[0],dp[i][j])
                temp.append(cur)
            else:
                if dp[i][j] and dp[i][j-item[1]]:
                    cur = min(dp[i][j],dp[i][j-item[1]]+item[0])
                elif dp[i][j]:
                    cur = dp[i][j]
                elif dp[i][j-item[1]]:
                    cur = dp[i][j-item[1]]+item[0]
                temp.append(cur)
            if cur and cur<=w:
                ans = max(ans,j)
        dp.append(temp)
    print(ans)

                    
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

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

def main():
    N, W = map(int,input().split())
    WG = [0]
    V = [0]
    for i in range(N):
        w, v = map(int,input().split())
        WG.append(w)
        V.append(v)
    
    dp = [[float('inf')]*(max(V)*N+1) for _ in range(N+1)]
    dp[0][0] = 0
    
    for i in range(1,N+1):
        for v in range(0,max(V)*N+1):
            if v-V[i] < 0:
                dp[i][v] = dp[i-1][v]
                continue
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i]]+WG[i])
    
    ans = 0
    for i in range(max(V)*N+1):
        if dp[N][i] <= W:
            ans = i
            
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
N,W = map(int,input().split())
w = [-1]
v = [-1]
for i in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
INF = 10**11+1
dp = [[INF]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
    for j in range(0,10**5+1):
        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 = 10**5
while dp[N][ans]>W:
    ans -= 1
print(ans)

Solution (Python):
import math

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

DP = [[math.inf] * 100001 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(100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

ans = 100000
while DP[N][ans] > W:
    ans -= 1
print(ans)

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



N, W = inpl()
INF = 10**12
dp = [[INF] * 100001 for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    w, v = inpl()
    for j in range(0, 100001):
        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]
            
ans = 100000
while dp[N][ans] > W:
    ans -= 1

_debug(dp[N][ans])
print(ans)

Solution (Python):
"""メモリ足りねぇ..."""

import sys
pin=sys.stdin.readline

INF=10**10
N,W=map(int,pin().split())

dp=[[INF]*100001 for _ in [0]*(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  w,v=pin().split()
  w=int(w)
  v=int(v)
  for j in range(100001):
    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]
ans=100000
while dp[N][ans]>W:
  ans-=1
print(ans)

Solution (Python):
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [float('inf')] * 10 ** 6
DP[0] = 0
for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if w + d > W:
            continue
        D[i + v] = min(DP[i + v], w + d)
    DP = D
ans = 0
for i, d in enumerate(DP):
    if d == float('inf'):
        continue
    ans = i
print(ans)

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

dp = [[float('inf') for i in range(10**5+1)] for j 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(0, 10**5+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]
    
    
ans = 10**5
while(dp[N][ans])>W:
  ans -= 1
print(ans)

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

Solution (Python):
def main():
    N, W = map(int, input().split())
    max_val = 10 ** 5
    dp = [[float('inf')]*(max_val + 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(max_val + 1): 
            if j - v < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min([
                    dp[i-1][j-v] + w,
                    dp[i-1][j]
                ])

    for i, w in enumerate(reversed(dp[-1])):
        if w <= W:
            print(max_val - i)
            exit()


if __name__ == '__main__':
    main()

Solution (Python):
n,W = map(int,input().split())
wl = []
vl = []
for i in range(n):
    w,v =  map(int,input().split())
    wl.append(w)
    vl.append(v)
s = sum(vl)

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


for i in range(n):
    for j in range(s+1):
        if vl[i]-j>0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i][j-vl[i]]+wl[i])
        
        
ans = 0
for i in range(n+1):
    for j in range(s+1):
        if dp[i][j]<=W:
            ans = max(ans,j)
print(ans)

Solution (Python):
n,w=map(int, input().split())
g=[0]
v=[0]
for i in range(n):
    G,V=map(int, input().split())
    g.append(G)
    v.append(V)

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

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

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

Solution (Python):
import numpy as np
import warnings
warnings.filterwarnings('ignore')

Mv = 10 ** 5
Mw = 10 ** 11

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

V = np.max(v)


dp = np.array([[Mw] * (Mv + 1)] * (N+1))
dp[0][0] = 0
for i in range(1, N+1):
    tmp_arr = np.full(Mv+1, Mw, dtype=int)
    tmp_arr[v[i]:] = dp[i-1][:-v[i]] + w[i]
    dp[i] = np.minimum(dp[i-1], tmp_arr)

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

Solution (Python):
n,w = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(n)]
inf = float("inf")
dp = [[inf]*(100000+1) for _ in range(n+1)]
dp[0][0] = 0
ans = 0
for i in range(n):
    for v in range(100001):
        if v - ls[i][1] >= 0:
            dp[i+1][v] = min(dp[i][v],dp[i][v-ls[i][1]]+ls[i][0])
        else:
            dp[i+1][v] = dp[i][v]
for j in range(100001):
    if dp[n][j] <= w:
        ans = j
print(ans)

Solution (Python):
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)
dp = [[float('inf')]*(max(v)*N+1) for _ in range(N+1)]
dp[0][0] = 0

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

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

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)

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

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

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

Solution (Python):



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

INF = 10**10


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



dp[0][0] = 0


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


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

Solution (Python):
N,W=[int(x) for x in input().split()]
w=[-1 for _ in range(N)]
v=[-1 for _ in range(N)]
for i in range(N):
	w[i],v[i]=[int(x) for x in input().split()]



dp=[1000000002 for _ in range(100001)]
dp[0]=0
for i in range(N):
	for v_ in range(100000,v[i]-1,-1):
		
		dp[v_]=min(dp[v_],dp[v_-v[i]]+w[i])
for v_ in range(100000,-1,-1):
	if dp[v_]<=W: print(v_); break

Solution (Python):
n, W = map(int, input().split())
inf = 10 ** 10
V = 10 ** 5
dp = [inf for _ in range(V + 1)]
dp[0] = 0
ans = 0
for _ in range(n):
    w, v = map(int, input().split())
    for i in range(V, v - 1, -1):
        dp[i] = min(dp[i], dp[i - v] + w)
        if dp[i] <= W:
            ans = max(ans, i)
print(ans)

Solution (Python):
n, w = map(int, input().split())
INF = float('inf')
P = []
for _ in range(n):
    iw, iv = map(int, input().split())
    P.append([iw, iv])

dp = [[INF for i in range(10 ** 5 + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(10 ** 5 + 1):
        if j - P[i - 1][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - P[i - 1][1]] + P[i - 1][0])
        else:
            dp[i][j] = dp[i - 1][j]

ans = 10 ** 5
while dp[n][ans] > w:
    ans -= 1
print(ans)

Solution (Python):
n,W = map(int,input().split())
w,v = [],[]
for i in range(n):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
mv = sum(v)
INF = float("INF")
dp = [[INF]*(mv+100) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for sv in range(mv+100):
        if sv-v[i] >= 0:
            dp[i+1][sv] = min(dp[i+1][sv],dp[i][sv-v[i]]+w[i])
        dp[i+1][sv] = min(dp[i+1][sv],dp[i][sv])
    
ans = 0
for i in range(mv+100):
    
    if dp[n][i] <= W:
        ans = max(ans,i)
print(ans)

Solution (Python):
import numpy as np

N, W = map(int, input().split())
knap = []
for i in range(N):
    knap.append(tuple(map(int, input().split())))

s_val = sum([v for w, v in knap])
    
INF = float("inf")
dp = np.full(s_val+1, INF)
dp[0] = 0

for i, (w, v) in enumerate(knap):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
    
print(max([i for i in range(s_val+1) if dp[i] <= W]))

Solution (Python):



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

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


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


ans=0
for i in range(10**5+1):
    if dp[i]<=W:
        ans=i

print(ans)

Solution (Python):
def edu_dp_e_knapsack2():
    n, c = map(int, input().split())
    w, v = [0], [0]
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[float('inf')] * 100001 for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(0, 100001):
            dp[i][j] = dp[i - 1][j]
            if j >= v[i]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i])
    ans = 100000
    while dp[n][ans] > c: ans -= 1
    print(ans)
edu_dp_e_knapsack2()

Solution (Python):
INF = 1e10
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]
data = [[INF, INF]] + data

max_value = n * 1000

dp = [[INF] * (max_value + 1) for _ in range(n + 1)]

dp[0][0] = 0

for i in range(1, n + 1):
    for j in range(max_value + 1):
        wi, vi = data[i][0], data[i][1]
        
        take = dp[i - 1][j - vi] + wi if j - vi >= 0 else INF
        
        dismiss = dp[i - 1][j]
        dp[i][j] = min(take, dismiss)


result = dp[-1]
for j in reversed(range(max_value + 1)):
    if result[j] <= w:
        print(j)
        break

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

w = [0]
v = [0]

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

dp = [[float('inf') for a in range(110000)] for b in range(N+1)]
dp[0][0] = 0

ans = 0

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

        if dp[i][j] <= W and j > ans:
            ans = j

print(ans)

Solution (Python):
import numpy as np
N,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(N)]
vmax=sum([v for w,v in a])
INF=float("inf")
dp=np.full(vmax+1,INF)
dp[0]=0

for i in range(N):
    w,v=a[i]
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
print(max([i for i in range(vmax+1) if dp[i]<=W]))

Solution (Python):
import numpy as np

N, W = map(int, input().split())
a = [list(map(int,input().split())) for _ in range(N)]
vmax = sum([a[i][1] for i in range(N)])
INF = float('inf')
dp = np.full(vmax+1, INF)
dp[0] = 0

for i in range(N):
  w, v = a[i-1]
  dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(max([i for i in range(vmax+1) if dp[i] <= W]))

Solution (Python):
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    Vmax = max(v)*N
    INF = 10**9

    dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
    dp[0][0]=0

    for i in range(N):
        tmp = np.ones(Vmax+1,dtype=int)*INF
        if i==0:tmp[0]=0
        tmp[v[i]:] = dp[i][:-v[i]] + w[i]
        dp[i+1] = np.minimum(dp[i],tmp)

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

Solution (Python):

import numpy as np
N,W = map(int,input().split())
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)
    
Vmax = max(v)*N
INF = 10**9
            
dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
dp[0][0]=0

for i in range(N):
    tmp = np.ones(Vmax+1,dtype=int)*INF
    tmp[v[i]:] = dp[i][:-v[i]] + w[i]
    dp[i+1] = np.minimum(dp[i],tmp)

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

Solution (Python):
import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]

dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
  
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()

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

v=[]
w=[]
for i in range(N):
    w_i,v_i=map(int,input().split())
    w.append(w_i)
    v.append(v_i)

sum_v=sum(v)+1
dp=[[float('inf')]*(sum_v) for i in range(N+1)] 
dp[0][0]=0

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

ans=0
for i in range(1,sum_v):
  if dp[N][i] <= W:
    ans = i
print(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)
sum_v = sum(v_list)+1

dp = [[float('INF')]*(sum_v) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = w_list[i], v_list[i]
    for j in range(sum_v):
        if v<=j: dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
        else: dp[i+1][j] = dp[i][j]
for i in range(sum_v-1, -1, -1):
    if dp[-1][i] <= W:
        print(i)
        break

Solution (Python):

"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

print(dp[n-1])
n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))
"""

n, W = [int(i) for i in input().split(' ')]

dp = [10**9+7]*(10**5+1)
dp[0] = 0
for _ in range(n):
    curwt, val = [int(i) for i in input().split(' ')]
    for v in range((10**5) - val, -1, -1):
        dp[v+val] = min(dp[v+val], dp[v]+curwt)

ans = 0
for i, val in enumerate(dp):
    if val <= W:
        ans = max(i, ans)

print(ans)

Solution (Python):
n,w=map(int,input().split())
INF=float('inf')
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])

dp=[[INF for i in range(10**5+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  for j in range(10**5+1):
    if j-P[i-1][1]>=0:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-P[i-1][1]]+P[i-1][0])
    else:
      dp[i][j]=dp[i-1][j]
      
ans=10**5
while dp[n][ans]>w:
  ans-=1
print(ans)