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

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return


def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return


def F():
    return


def G():
    return


def H():
    return


def I():
    return 























if __name__ == '__main__':
    E()

Solution (Python):



import sys

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

dp = [float('inf')] * (sum(v)+1)
dp[0] = 0

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

Solution (Python):
n,w=map(int,input().split())
l=(n*1000)+1
dp=[9999999999]*(l)
dp[0]=0
for i in range(n):
	wt,val=map(int,input().split())
	for j in range(l-1,val-1,-1):
		dp[j]=min(dp[j],dp[j-val]+wt)
for i in range(l-1,-1,-1):
	if dp[i]<=w:
		print(i)
		exit()

Solution (Python):
n,w=map(int,input().split())
dp=[999999999999999]*(100001)
dp[0]=0
for i in range(n):
	wt,val=map(int,input().split())
	for j in range(100000,val-1,-1):
		dp[j]=min(dp[j],dp[j-val]+wt)
for i in range(100000,-1,-1):
	if dp[i]<=w:
		print(i)
		exit()

Solution (Python):
n, w = map(int, input().split())

weight = []
value = []

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

max_v = sum(value)


inf = float("inf")
dp = [[inf]*(max_v+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j - value[i] >= 0:
            dp[i+1][j] = dp[i][j-value[i]]+weight[i]
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(max_v+1):
    if dp[n][j] > w:
            continue
    else:
        ans = max(ans, j)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

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

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

def ans(N, W):
    d = [W+1] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

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

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

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

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


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

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

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

def f(n, W):
    dp = [float('inf')] * (100010)
    dp[0] = 0
    maxv = 0
    for i in range(n):
        wi, vi = map(int, input().split())
        maxv += vi
        for v in range(maxv, -1, -1):
            w_ = wi if v - vi < 0 else dp[v - vi] + wi
            if dp[v] > w_ and w_ <= W:
                dp[v] = w_
    return(dp.index(float('inf')) - 1)

n, w = map(int, input().split()) 
print(f(n, w))

Solution (Python):
def e_knapsack2(N, W, Goods):
    """
    Dと同じ設定だが、制約が違う(1 <= v_i <= 10^3 と価値の制約がゆるめ)
    """
    import numpy as np
    
    
    
    max_value = np.sum(np.array(Goods), axis=0)[1]
    dp = np.full(max_value + 1, W + 1, dtype='int64')
    dp[0] = 0  
    for w, v in Goods:
        
        
        np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
    return np.max(np.where(dp <= W))

N, W = [int(i) for i in input().split()]
Goods = [[int(i) for i in input().split()] for j in range(N)]
print(e_knapsack2(N, W, Goods))

Solution (Python):
from sys import stdin
n,W=map(int,input().split())
INF=1<<60
sum_v=0
vector=[]
for i in range(n):
    w,v=map(int,stdin.readline().split())
    sum_v+=v
    vector.append((w,v))

dp=[INF for i in range(sum_v+1)]
dp[0]=0

for w,v in vector:
    for j in range(sum_v-v,-1,-1):
        dp[v+j]=min(dp[v+j],dp[j]+w)

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

Solution (Python):
N, W = list(map(int,raw_input().split()))
dp = [float("inf") for i in range(100001)]
dp[0] = 0
for i in xrange(N):
  wi, vi = list(map(int,raw_input().split()))
  for v in xrange(100000-vi, -1, -1):
    dp[v+vi] = min(dp[v+vi],dp[v]+wi)
print(max([v for v in xrange(100001) if dp[v]<=W]))

Solution (Python):
n, m = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(n)]
s = sum(list(map(lambda x: x[1], goods)))
dp = [[10 ** 15 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(s+1):
        w, v = goods[i]
        if j >= v:
            dp[i+1][j] = min(dp[i][j], dp[i][j - v] + w)
        else: dp[i+1][j] = dp[i][j]
maxv = 0
for j in range(s+1):
    if dp[n][j] <= m:
        maxv = j
print(maxv)

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

Solution (Python):
if __name__ == '__main__':
    N, W = map(int,input().split(" "))
    w,v = [0]*(N+1),[0]*(N+1)
    for i in range(N):
        w[i+1],v[i+1] = map(int,input().split(" "))

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

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

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

Solution (Python):


"""
Created on 2019/3/2
Update on 2019/3/5
Solved on 2019/3/
@author: shinjisu
"""




import numpy as np


def getInt(): return int(input())



def getIntList(): return np.array(input().split(), dtype=np.longlong)



def zeros(n): return np.zeros(n, dtype=np.longlong)



def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n):  
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat
def getIntMat(n, m): 
    mat = zeros((n, m))
    for i in range(n):
        mat[i] = getIntList()
    return mat


def zeros2(n, m): return [zeros(m)]*n 


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_A():  
    N = getInt()
    H = getIntList()
    dmp((N, H), 'N, H')
    c = zeros(N)
    c[1] = abs(H[1]-H[0])
    for i in range(2, N):
        c[i] = min(c[i-1] + abs(H[i]-H[i-1]),
                   c[i-2] + abs(H[i]-H[i-2]))
    dmp(c, 'c')
    return c[N-1]


def prob_B_TLE():  
    N, K = getIntList()
    H = getIntList()
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N)
    c[0] = 0
    for i in range(1, N):
        
        for j in range(max(0, i-K), i):
            c[i] = min(c[i], c[j] + abs(H[i]-H[j]))
    dmp(c, 'c')
    return c[N-1]


def prob_B():  
    N, K = getIntList()
    H = np.array(input().split(), dtype='int')
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N, dtype=np.longlong)
    c[0] = 0
    for i in range(1, N):
        c[i] = np.min(c[max(0, i-K):i] + np.abs(H[max(0, i-K):i] - H[i]))
    dmp(c, 'c')
    return c[N-1]


def prob_C():  
    N = getInt()
    a = zeros(N)
    b = zeros(N)
    c = zeros(N)
    for i in range(N):
        a[i], b[i], c[i] = getIntList()
    dmp(N, 'N')
    dmp(a, 'a')
    dmp(b, 'b')
    dmp(c, 'c')
    dpa = zeros(N)
    dpb = zeros(N)
    dpc = zeros(N)
    dpa[0] = a[0]
    dpb[0] = b[0]
    dpc[0] = c[0]
    for i in range(1, N):
        dpa[i] += max(dpb[i-1], dpc[i-1]) + a[i]
        dpb[i] += max(dpc[i-1], dpa[i-1]) + b[i]
        dpc[i] += max(dpa[i-1], dpb[i-1]) + c[i]
    dmp(dpa, 'dpa')
    dmp(dpb, 'dpb')
    dmp(dpc, 'dpc')
    return max(dpa[N-1], dpb[N-1], dpc[N-1])


def prob_D_incomplete():  
    N, W = getIntList()
    w = zeros(N)
    v = zeros(N)
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp((N, W), 'N, W')
    dmp(w, 'w')
    dmp(v, 'v')
    dpw = zeros(N)
    dpv = [0]*N
    knap = zeros(N)  
    dpw[0] = w[0]
    dpv[0] = v[0]
    knap[0] = 1
    for i in range(1, N):
        if dpw[i-1]+w[i] <= W:
            dpw[i] = dpw[i-1] + w[i]
            dpv[i] = dpv[i-1] + v[i]
            knap[i] = 1
            continue
        swap = -1
        maxV = -INF
        minW = INF
        for j in range(0, i):
            if v[i] > v[j] and knap[j] == 1 and dpw[i-1]-w[j]+w[i] <= W:
                if v[j] >= maxV:
                    maxV = v[j]
                    swap = j
            elif v[i] == v[j] and knap[j] == 1 \
                    and dpw[i-1]-w[j]+w[i] <= W and w[i] < w[j]:
                if w[j] <= minW:
                    minW = w[j]
                    swap = j
        if swap > 0:
            dpw[i] = dpw[i-1] - w[j] + w[i]
            dpv[i] = dpv[i-1] - v[j] + v[i]
            knap[i] = 1
            knap[j] = 0
        else:
            dpw[i] = dpw[i-1]
            dpv[i] = dpv[i-1]

    dmp(dpw, 'dpw')
    dmp(dpv, 'dpv')
    dmp(knap, 'knap')
    return dpv[N-1]


def prob_D():  
    N, W = getIntList()
    w, v = zeros(N), zeros(N)
    dmp((N, W))
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp(w, 'weight')
    dmp(v, 'value')
    dp = zeros(W+1)
    dmp(dp.size)
    for i in range(N):
        dmp(dp, 'dp')
        dmp(w[i], 'w[i]')
        dp[w[i]:] = np.maximum(dp[w[i]:],
                               dp[:W-w[i]+1] + v[i])
    dmp(dp, 'dp')
    return dp[W]


def prob_E():  
    N, W = getIntList()
    w, v = zeros(N), zeros(N)
    dmp((N, W))
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp(w, 'weight')
    dmp(v, 'value')
    dp = zeros(v.sum()+1)
    dp += w.sum()+1
    dp[0] = 0
    dmp(dp.size, 'dp.size')
    for i in range(N):
        dmp((w[i], v[i], dp), 'w[i], v[i], dp')
        
        
        """
        for j in range(v[i], v.sum()+1):
            
            if dp[j] == 0:
                dp[j] = dp[j-v[i]] + w[i]
                dmp((j,dp), '0-dp')
            elif dp[j] > dp[j-v[i]] + w[i]:
                dp[j] = dp[j-v[i]] + w[i]
                dmp((j,dp), 'dp')
        """
        dp[v[i]:] = np.minimum(dp[v[i]:],
                               dp[:v.sum()-v[i]+1] + w[i])
    dmp(dp, 'final dp')
    maxVal = 0
    minWeight = INF
    for i in range(len(dp)):
        if dp[i] <= W and i >= maxVal:
            maxVal = i
    dmp(maxVal)
    return maxVal


debug = False  
ans = prob_E()
print(ans)

Solution (Python):
import numpy as np
n, wt = map(int, input().split())
 
d = np.full(n*1000+1,wt+1, 'i8')
d[0] = 0
for _ in range(n):
  w, v = map(int, input().split())
  d[v:] = np.minimum(d[v:], d[:-v]+w)
print(np.max(np.where(d<=wt)))

Solution (Python):

"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0.0] * n, [0] * n
for i in range(n):
    wi, vi = input().split()
    w[i], v[i] = float(wi), int(vi)

max_val = sum(v)
dp = [[float('inf')] * (max_val + 1) for _ in range(n)]
for i in range(n):
    dp[i][0] = 0.0

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

print(int(max(i for i, val in enumerate(dp[-1]) if val <= m)))

Solution (Python):

N, W  = (int(i) for i in input().split()) 
w = []
v = []
for i in range(N):
    aa, bb = [int(i) for i in input().split()] 
    w.append(aa)
    v.append(bb)



maxval = 100001
dp = [[1000000000000 for i in range(maxval)] for j in range(N+1)]
dp[0][0] = 0

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

mv = 0
for i in range(N+1):
    for j in range(maxval):
        j0 = maxval - 1 - j
        if dp[i][j0] <= W:
            if mv < j0:
                mv = j0

print(mv)

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

supremum = 10**5

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

for i in range(N) :
    weight_i,value_i = L[i]    
    for value in range(supremum,value_i-1,-1) :
        if dp[value-value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value-value_i] + weight_i)

for i in range(supremum,-1,-1) :
    if dp[i] < float("inf") :
        ans = i
        break

print(ans)

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

supremum = 10**5

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

for i in range(N) :
    weight_i,value_i = L[i]    
    for value in range(supremum,value_i-1,-1) :
        if dp[value-value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value-value_i] + weight_i)

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

print(ans)

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

supremum = 10**5

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

for i in range(N) :
    weight_i,value_i = L[i]    
    for j in range(supremum,value_i-1,-1) :
        if dp[j-value_i] < float("inf") :
            dp[j] = min(dp[j], dp[j-value_i] + weight_i)

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

print(ans)

Solution (Python):
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=sum(w)+1
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in reversed(range(1,total_v+1)):
    if dp[i]<=W:
        print(i)
        break

Solution (Python):
import numpy as np
n,w = [int(x) for x in input().split()]
wv = np.array([[int(y) for y in input().split()] for z in range(n)],dtype=int)
sum_wv = np.sum(wv,axis=0)
sum_v = sum_wv[1]
sum_w = sum_wv[0]
dp = np.full(sum_v+1,sum_w,dtype="int")
dp[0] = 0
for wei,val in wv:
    dp[val:] = np.minimum(dp[val:],dp[:-val]+wei)
for p in range(sum_v,1,-1):
    if(dp[p] <= w):
        print(p)
        break

Solution (Python):
import itertools as itr
inf = int(1e9)
n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
vm = max(varr)    
vmax = int(n*vm)+1
dp = [[inf]*vmax for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
ans = 0
for i, j in itr.product(range(1,n+1), range(1,vmax)):
    jv = j-varr[i]
    if jv <0:
        jv = 0
    dp[i][j] = min(dp[i-1][jv] + warr[i], dp[i-1][j])
    if j > ans and dp[i][j] <= w:
        ans = j
  
print(ans)

Solution (Python):
N, W = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(N)]

INF = 10 ** 18
sup_v = 10 ** 5
DP = [INF] * (sup_v + 1)
DP[0] = 0

for w, v in V:
    for i in range(sup_v, -1, -1):
        DP[i] = min(DP[i], DP[i-v] + w)

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

Solution (Python):
N, W = map(int, input().split())
inf = 1 << 60

dp = [[inf for j in range(100001)] for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    wi, vi = map(int, input().split())
    for v in range(0, 100001):
        dp[i][v] = min(dp[i][v], dp[i - 1][v])
    for v in range(vi, 100001):
        dp[i][v] = min(dp[i][v], dp[i - 1][v - vi] + wi)

ans = [(i,v) for i,v in enumerate(dp[N])]
ans = list(filter(lambda e: e[1] <= W, ans))
ans = ans[-1][0]
print(ans)

Solution (Python):
import numpy as np
n,w = [int(x) for x in input().split()]
wv = np.array([[int(y) for y in input().split()] for z in range(n)],dtype=int)
sum_wv = np.sum(wv,axis=0)
sum_v = sum_wv[1]
sum_w = sum_wv[0]
dp = np.full(sum_v+1,sum_w,dtype="int")
dp[0] = 0
for wei,val in wv:
    dp[val:] = np.minimum(dp[val:],dp[:-val]+wei)
for p in range(sum_v,1,-1):
    if(dp[p] <= w):
        print(p)
        break

Solution (Python):
MAX_V = 100100
MAX_N = 101
INF = pow(2, 62)

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

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

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])



print(ans)

Solution (Python):
MAX_V = 100100
MAX_N = 101
INF = pow(2, 63)

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

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

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])



print(ans)

Solution (Python):
MAX_V = 100100
MAX_N = 101
INF = pow(2, 40)

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

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

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])



print(ans)

Solution (Python):
MAX_V = 100100
MAX_N = 101
INF = pow(2, 60)

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

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

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])



print(ans)

Solution (Python):
MAX_V = 100100
MAX_N = 101
INF = pow(2, 64)

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

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

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])



print(ans)

Solution (Python):
MAX_V = 100100
MAX_N = 101
INF = pow(2, 70)

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

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

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])



print(ans)

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

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

dp[0][0] = 0
for i in range(N):
    for j in range(sum_value + 1):
        if j - items[i][1] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - items[i][1]] + items[i][0])
        else:
            dp[i + 1][j] = dp[i][j]
for i in range(sum_value, -1, -1):
    w = dp[N][i]
    if w <= W:
        print(i)
        exit()

Solution (Python):

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

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


def solve():
    MaxV = 10**3*N+1
    dp = [[float('inf')]*MaxV for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for v in range(MaxV):
            if items[i-1][1] <= v:
                dp[i][v] = min(dp[i-1][v], dp[i-1]
                               [v-items[i-1][1]]+items[i-1][0])
            else:
                dp[i][v] = dp[i-1][v]
    ans = 0
    for i, v in enumerate(dp[N]):
        if v <= W:
            ans = i

    print(ans)


solve()

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())



N, W = 0, 0
Ws, Vs = [0], [0]


def set_inputs():
    global N, W, Ws, Vs
    N, W = get_list_of_int()
    ws, vs = [], []
    for _ in range(N):
        w, v = get_list_of_int()
        ws.append(w)
        vs.append(v)
    Ws, Vs = ws, vs


def main():
    set_inputs()
    value_sum = sum(Vs)
    weights = [inf] * (value_sum + 1)
    items = [0] * (value_sum + 1)
    weights[0] = 0
    for v in range(1, value_sum + 1):
        weights[v], items[v] = min((weights[v - Vs[i]] + Ws[i], items[v - Vs[i]] | 1 << i) if v - Vs[i] >= 0 and (items[v - Vs[i]] & 1 << i) == 0 else (inf, 0) for i in range(N))
    max_value = next(i for i in reversed(range(value_sum + 1)) if weights[i] <= W)
    print(sum(Vs[i] if items[max_value] & 1 << i > 0 else 0 for i in range(N)))


if __name__ == '__main__':
    main()

Solution (Python):
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(10**5+10) for _ in range(110)]

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

for v in reversed(range(10**5+1)):
    if dp[n][v] <= w:
        print(v)
        exit()

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

INF = pow(10,15)
SIZE = pow(10,5)+1

n,w = li()
wv = [tuple(li()) for _ in range(n)]

dp = [[INF]*(SIZE + 10) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for idx in range(n):
    wi, vi = wv[idx]
    for val in range(SIZE):
        if val - vi < 0:
            dp[idx+1][val] = min(dp[idx+1][val],
                                 dp[idx][val])
            
        else:
            dp[idx+1][val] = min(dp[idx+1][val],
                                 dp[idx][val-vi]+wi,
                                 dp[idx][val])
        

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

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

INF = pow(10,15)
SIZE = pow(10,5)+1

n,w = li()
wv = [tuple(li()) for _ in range(n)]

dp = [[INF]*(SIZE + 10) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for idx in range(n):
    wi, vi = wv[idx]
    for val in range(SIZE):
        if val - vi < 0:
            dp[idx+1][val] = min(dp[idx+1][val],
                                 dp[idx][val])
            
        else:
            dp[idx+1][val] = min(dp[idx+1][val],
                                 dp[idx][val-vi]+wi,
                                 dp[idx][val])
        

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