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):
n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
    
dp = [[float("Inf") for j in range(1000*n+1)] for i in range(n+1)]

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

for i,[W,V] in enumerate(v):
    for j in range(1000*n):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if dp[i][j] + W <= w:
            dp[i+1][j+V] = min(dp[i+1][j+V], dp[i][j] + W)
ans = 0
for i in range(1, n+1):
    for j in range(1000*n+1):
        if dp[i][j] <= w:
            ans = max(ans, j)
print(ans)

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)

xxx=sum(value)
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

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

ans=0
for i in range(xxx+1):
  if dp[-1][i]<=w:
    ans=max(ans,i)

print(ans)

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

dp=[[0]*(N+1)]+[[float('inf')]*(N+1)for _ in range(v_max)]
for v in range(1,v_max+1):
    for n in range(1,N+1):
        dp[v][n]=min((dp[v][n-1],dp[v-wv[n][1]][n-1]+wv[n][0]))

print(max(v for v in range(v_max+1) if dp[v][N]<=W))

Solution (Python):
from pprint import pprint

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

lim = 1
for i in range(n):
    lim += wv[i][1]

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

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

for i in reversed(range(lim)):
    if dp[-1][i] <= w:
        ans = i
        break
print(ans)

Solution (Python):
from pprint import pprint

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

lim = 1
for i in range(n):
    lim += wv[i][1]

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

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

ans = float('inf')

for i in reversed(range(lim)):
    if dp[-1][i] <= w:
        ans = min(i, ans)
        break
print(ans)

Solution (Python):
import numpy as np
[N,W]=[int(x) for x in input().split()]
wv=[[int(x) for x in input().split()] for i in range(N)]

dp=np.array([[10**10]*(10**5+1) for i in range(N)])

dp[0][wv[0][1]]=wv[0][0]
dp[0][0]=0

for i in range(1,N):
  last=10**5-wv[i][1]+2
  dp[i][wv[i][1]:]=np.minimum(dp[i-1][wv[i][1]:],dp[i-1][:last-1]+wv[i][0])
  dp[i][:wv[i][1]]=dp[i-1][:wv[i][1]]
ans=0
count=10**5
while(ans==0):
  if dp[N-1][count]<=W:
    ans=count
    break
  else:
    count=count-1
print(ans)

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



def ifvalid(i):
    if i<0:
        return False
    return True


def solve():
    n,W=sep()
    ar=[]
    for _ in range(n):
        ar.append(lis())
    inf=10**10
    dp=[[inf for i in range(100005)] for _ in range(n+5)]
    dp[0][ar[0][1]]=ar[0][0]
    for i in range(n):
        dp[i][0]=0
    ans=0
    if ar[0][0]<=W:
        ans=ar[0][1]
    for i in range(1,n):
        for v in range(1,100005):
            if ifvalid(v-ar[i][1]):
                dp[i][v]=min(dp[i-1][v],dp[i-1][v-ar[i][1]]+ar[i][0])
            else:
                dp[i][v]=dp[i-1][v]
            if dp[i][v]<=W:
                ans=max(v,ans)
    print(ans)








solve()

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

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

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

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

Solution (Python):
n,w=map(int,input().split())
l=[]
for i in range(n):
	l.append(list(map(int,input().split())))
max_val=1000*n
dp=[[float('inf') for i in range(max_val+1)] for j in range(n+1)]
dp[0][0]=0

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

for i in range(max_val,-1,-1):
	if(dp[n][i]<=w):
		print(i)
		break

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

Solution (Python):

INF = float("inf")


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

w = [-1]
v = [-1]
value_max = 0
for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)
    value_max += v_in


memo = [[-1] * (value_max + 1) for i in range(n + 1)]

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

for i in range(value_max + 1):
    memo[0][i] = INF


def dp(i, value):
    if memo[i][value] == -1:
        if value > v[i]:
            rest = dp(i - 1, value - v[i])
            if rest == INF:
                tar = INF
            else:
                tar = rest + w[i]
            memo[i][value] = min(dp(i - 1, value), tar)
        else:
            memo[i][value] = min(dp(i - 1, value), w[i])
    return memo[i][value]


ans = -1
OK_MAX = 0
NG_MIN = value_max + 1

while OK_MAX + 1 != NG_MIN:
    i = int((OK_MAX + NG_MIN) / 2)
    ans_tmp = dp(n, i)
    if ans_tmp <= tar_w:
        OK_MAX = i
    else:
        NG_MIN = i

ans = OK_MAX

print("{}".format(ans))

Solution (Python):
N, W = map(int, input().split())
w, v = [0], [0]
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)
DP = [[float('inf') for c in range(sum_V+1)] for i in range(N+1)]

for i in range(0, N+1):
    for c in range(0, sum_V+1):
        if i == 0:
            if c == 0:
                DP[i][c] = 0
        elif c - v[i] < 0:
            DP[i][c] = DP[i-1][c]
        else:
            DP[i][c] = min(DP[i-1][c], DP[i-1][c-v[i]] + w[i])
ans = sum_V
while (DP[N][ans] > W):
    ans -= 1
print(ans)

Solution (Python):
import numpy as np

N, W = map(int, input().split())
wv = [tuple(map(int,input().split())) for _ in range(N)]
vmax = sum([wv[i][1] for i in range(N)])
INF = 10**20
  
dp = np.full(vmax+1, INF)
dp[0] = 0

for i in range(N):
  w,v = wv[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):
N,W=map(int,input().split())
wv = [tuple(map(int,input().split())) for _ in range(N)]

V = sum([wv[i][1] for i in range(N)])

dp = [W+1] * (V + 1)
dp[0] = 0
for i in range(N):
  w,v=wv[i]
  for j in range(V, v-1, -1):
    dp[j] = min(dp[j-v] + w, dp[j])
    
print(max(i for i in range(V+1) if dp[i] <= W))

Solution (Python):
n,w = [int(x) for x in input().split()]
wts = []
vals = []
for i in range(n):
    wi,vi = [int(x) for x in input().split()]
    wts.append(wi)
    vals.append(vi)

valsum = sum(vals)
dp = []
maxval = 0
for i  in range(n):
    dp.append([float('inf')]*(valsum+1))

for j in range(valsum+1):
    if j==vals[0]:
        dp[0][j] = wts[0]
        if wts[0]<=w:
            maxval = max(maxval,j)

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

for i in range(1,n):
    for j in range(1,valsum+1):
        if j>=vals[i]:
            dp[i][j] = min(dp[i-1][j-vals[i]]+wts[i],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
        if dp[i][j]<=w:
            maxval = max(maxval,j)
print(maxval)

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

INF = 10**9+1

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

for i in range(N):
    for j in range(V):
        if j >= wv[i][1]:
            DP[i+1][j] = min(DP[i][j], DP[i][j-wv[i][1]]+wv[i][0])
        else:
            DP[i+1][j] = min(DP[i][j], wv[i][0])
        
ans = 0
for i in range(N+1):
    for j in range(V+1):
        if DP[i][j] <= W:
            ans = max(ans, j+1)
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())
w=[0]+w
v=[0]+v
INF=float('inf')
dp=[[INF for i in range(N+1)] for j in range(10**5+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(10**5+1):
        if j-v[i]>=0:
            dp[j][i]=min(dp[j-v[i]][i-1]+w[i],dp[j][i-1])
        else:
            dp[j][i]=dp[j][i-1]
t=True
n=1
while t:
    if dp[-n][N]<=W:
        print(10**5-n+1)
        t=False
    else:
        n+=1

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) 
chmin(dp[i+1,j] , dp[i, j]) 
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, 2 * V_max), 10**12, dtype=np.int64)
    
    dp[0][0] = 0  

    
    for i in range(N):
        
        for j in range(V_max):
            jv = j + V[i]
            dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) 
chmin(dp[i+1,j] , dp[i, j]) 
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    
    dp[0][0] = 0  

    
    for i in range(N):
        dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
        dp[i + 1, V[i]:] = np.minimum(dp[i + 1, V[i]:], dp[i, :-V[i]] + W[i])
        
        
        
        
        
        

    
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


import numpy as np


N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) 
chmin(dp[i+1,j] , dp[i, j]) 
'''



def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    
    dp[0][0] = 0  

    
    for i in range(N):
        dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
        dp[i + 1, V[i]:] = np.minimum(dp[i + 1, V[i]:], dp[i, :-V[i]] + W[i])
        
        
        
        
        

    
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) 
chmin(dp[i+1,j] , dp[i, j]) 
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    
    dp[0,0] = 0  

    
    for i in range(N):
        dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
        for j in range(V_max):
            jv = j + V[i]
            if jv>=V_max:
              break
            dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])

    
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) 
chmin(dp[i+1,j] , dp[i, j]) 
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    
    dp[0][0] = 0  

    
    for i in range(N):
        for j in range(V_max):
            jv = j + V[i]
            if jv < V_max:
                dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Solution (Python):
import numpy as np

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 = np.full(10**3 *n +1, 10**18)
dp[0] = 0

for i in range(n):
  dp[v[i]:] = np.minimum(dp[v[i]:], dp[:-v[i]]+w[i])
  
ans = 0
for i in range(10**3 *n, -1, -1):
  if dp[i] <= W:
    ans = i
    break
    
print(ans)

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

Vmax = 10**3*100
dp = [[float('inf')]*(Vmax+1) for i in range(N+1)]
dp[0][0]=0

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

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

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




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

for i in range(1, N + 1):
    for j in range(0, 100001):
        
        if j - wv[i][1] >= 0:
            
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        
        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 = [[0, 0]]
for _ in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])


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

for i in range(1, N + 1):
    for j in range(0, 100001):
        
        if j - wv[i][1] >= 0:
            
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        
        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())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    weight,value=a[i]
    for j in range(10**5+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+value<=10**5:
            dp[i+1][j+value]=min(dp[i][j+value],dp[i][j]+weight)
for i in range(10**5+1):
    if dp[-1][-i-1]<=W:
        print(10**5-i)
        break

Solution (Python):
n,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
m=sum([a[i][1] for i in range(n)])
dp=[[float('inf') for _ in range(m+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    weight,value=a[i]
    for j in range(m+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+value<=m:
            dp[i+1][j+value]=min(dp[i][j+value],dp[i][j]+weight)
for i in range(m+1):
    if dp[-1][-i-1]<=W:
        print(m-i)
        break

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

dp=[inf]*100001
dp[0]=0


for i in range(0,n):
    nextdp=[inf]*100001
    x=[int(i) for i in input().split()]
    for j in range(100001):
        if x[1] <= j:
            nextdp[j]=min(dp[j],x[0]+dp[j-x[1]])
        else:
            nextdp[j]=dp[j]
    dp=nextdp


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

Solution (Python):
import math

n, W = map(int, input().split())
costs, weights = [], []
sum_vals = 0
for i in range(n):
    a,b =map(int, input().split())
    sum_vals+=b
    costs.append(b)
    weights.append(a)
dp = [int(10e18)+1]*(sum_vals+1)
dp[0] = 0
for item in range(0, n):
    for value_already in range(sum_vals-costs[item], -1, -1):
        dp[value_already+costs[item]] = min(dp[value_already+costs[item]], dp[value_already]+weights[item])
ans = 0
for i in range(1, sum_vals+1):
    if(dp[i]<= W):
        ans = max(ans, i)
print(ans)

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

n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

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

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

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

print(ans)

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

n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

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

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

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

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())
inf = float('inf')    
dp=[[inf for i in range(N+1)] for j in range(N*1000+1)] 

dp[0][0]=0

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


            
for i in reversed(range(N*1000+1)):
    if dp[i][N]<=W:
        print(i)
        break

Solution (Python):
def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)

    
    
    INF = 10 ** 9 + 1
    max_v = sum(values)
    dp = [[INF] * (max_v + 1) for _ in range(item_count)]
    for i in range(item_count):
        dp[i][0] = 0
    ans = 0
    for item_i in range(item_count):
        for sum_v in range(1, max_v + 1):
            v = values[item_i]
            if v <= sum_v:
                min_w = min(
                    
                    
                    dp[item_i - 1][sum_v - v] + weights[item_i],
                    dp[item_i - 1][sum_v])
            else:
                min_w = dp[item_i - 1][sum_v]
            dp[item_i][sum_v] = min_w
            if min_w <= capacity:
                ans = max(ans, sum_v)
    print(ans)


if __name__ == '__main__':
    main()

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

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

Solution (Python):
n, W = map(int,input().split())
dp = [W+1]*(10**5 + 1)
vr=[]
for i in range(n):
  w,v= map(int,input().split())
  vr.append(v)
  if i==0:
  	dp[v]=w
  for j in range(10**5-v,-1,-1):
  	cw=w+dp[j]
  	if j==v and vr.count(v)==1:
  		continue
  	if cw<=W:
  		dp[j+v]=min(dp[j+v],cw)
  dp[v]=min(w,dp[v])

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

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())
v_max = sum(v_list)
dp = [10 ** 9 + 1] * (v_max + 1)

for i, v in enumerate(v_list):
    for j in range(v_max, 0, - 1):
        x = dp[j] + w_list[i]
        if x <= w and x < dp[j + v]:
            dp[j + v] = x
    dp[v] = min(dp[v], w_list[i])

for v in range(v_max, -1, -1):
    if dp[v] <= w:
        print(v)
        quit()

Solution (Python):
N, W = map(int, input().split())
ITEM = []
vmax, wmax = 0,0
for _ in range(N):
  w,v = map(int, input().split())
  ITEM.append((v,w))
  vmax = max(vmax,v)
  wmax = max(wmax,w)

INF = 10**18
    
def solve1():
  
  
  dp = [INF] * (vmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    
    for v in range(vmax*i,-1,-1):
      if v-v1>=0:
        dp[v] = min(dp[v], dp[v-v1]+w1)
  ret = 0
  for i in range(len(dp)):
    if dp[i] <= W:
      ret = max(ret, i)
  
  return ret

ans = solve1()
  
print(ans)

Solution (Python):
N, W = map(int, input().split())
ITEM = []
vmax, wmax = 0,0
for _ in range(N):
  w,v = map(int, input().split())
  ITEM.append((v,w))
  vmax = max(vmax,v)
  wmax = max(wmax,w)

INF = 10**18
    
def solve1():
  
  
  dp = [INF] * (vmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    
    for v in range(vmax*i,-1,-1):
      if v-v1>=0:
        dp[v] = min(dp[v], dp[v-v1]+w1)
  ret = 0
  for i in range(len(dp)):
    if dp[i] <= W:
      ret = max(ret, i)
  
  return ret

ans = solve1()
  
print(ans)

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

dp = [[1000000001] * 100001 for _ in range(N + 1)] 
dp[0][0] = 100000001
ans = 0
for i in range(1, N + 1):
    for j in range(1, 100001):
        if v[i] < j:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
        else:
            dp[i][j] = min(dp[i - 1][j], w[i])


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

Solution (Python):
import numpy as np
import numba
import math

@numba.njit
def main():
    dpt = np.array([math.inf] * (10**3*N + 1))
    dpt[0] = 0
    for i in range(N):
        for j in range(len(dpt)-1, items[i][1]-1, -1):
            dpt[j] = min(dpt[j], dpt[j-items[i][1]]+items[i][0])

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

if __name__ == '__main__':
    N, W = map(int, input().split())
    items = np.array([list(map(int, input().split())) for i in range(N)])
    main()