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



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



VMAX = 10**3 * (10**2)

tab = [ [10**10] *(VMAX+1) for _ in range(n+1)]



for i in range(1, len(wvn)+1 ):
    
    wv = wvn[i-1]
    wi = wv[0]
    vi = wv[1]
    
    for j in range( VMAX + 1 ):

        t = tab[i-1][j]
        
        if j >= vi:
            t = min(t, tab[i-1][j-vi]+wi)

        else:
            t = min(t, wi)
        
        tab[i][j] = t

ans = 0
while tab[n][ans] <= w:
    
    ans += 1


print(ans)



def debug0():
    row1 = tab[1]
    
    print("DEBUG0--START")
    print([(i, row1[i]) for i in range(0,50,5)])
    print("DEBUG0--END")



def debug1():

    for i in range(n+1):
        t = tab[i][0]
        sss = set(tab[i])
        print(sss)
        for j in range( 1, len(tab[i]) ):
            v = tab[i][j]

            if not t == v:
                t = v
                print( (i,j,v) )
 


def debug3():
    t = -1

    for i in range( len(tab[n])-1 ):
        e = tab[n][i]

        if not t == e:
            t = e
            print( (i, e) )
            






def debug2():
    t = -1
    for vi in range(len(tab[0])):

        v = tab[n][vi]
        if not t == v:
            t = v
            print((t,vi))

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    max_val = 0
    for i in range(N):
        max_val += WV[i][1]
    max_val += 1
    
    dp = [[inf] * max_val for i in range(N)]
    for v in range(max_val):
        if v <= WV[0][1]:
            dp[0][v] = WV[0][0]
        else:
            break
    for i in range(1, N):
        for v in range(max_val):
            if v >= WV[i][1]:
                
                
                dp[i][v] = min(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
            else:
                dp[i][v] = dp[i - 1][v]
            if v <= WV[i][1]:
                dp[i][v] = min(dp[i][v], WV[i][0])

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


if __name__ == '__main__':
    main()

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

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

Solution (Python):


MAX_V = 10**5
INF = 10**10
N, W = list(map(int, input().split()))

dp = [[INF for _ in range(MAX_V+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = list(map(int, input().split()))
    for over_v in range(MAX_V+1):
        if over_v - v < 0:
            dp[i][over_v] = dp[i-1][over_v]
            continue
        dp[i][over_v] = min(dp[i-1][over_v-v] + w, dp[i-1][over_v])

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

Solution (Python):
import numpy as np

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

w = np.zeros(N+1, dtype = int)
v = np.zeros(N+1, dtype = int)

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

max_v = v.sum()

dp = np.ones((N+1, max_v + 1), dtype =int) * 10**9
dp[0,0] = 0

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


ans = 0
for i, j in enumerate(dp[N,:]):
    if j <= W:
        ans = i

print(ans)

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

cost = [list(map(int,input().split())) for i in range(N)]


dp = [[float('inf')] * (100001) for i in range(N)]


for i in range(N):
    for j in range(100001):
        if j == 0:
            dp[i][j] = 0

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

ans = float('inf')

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

Solution (Python):
n,W=map(int,input().split())
w_list=[0]
v_list=[0]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
dp=[]
for i in range(n+1):
    sub_list=[]
    for j in range(100001):
        sub_list.append(0)
    dp.append(sub_list)
for j in range(100001):
    if j==0:
        dp[0][0]=0
    else:
        dp[0][j]=10**10
for i in range(1,n+1):
    for j in range(100001):
        if v_list[i]<=j:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-v_list[i]]+w_list[i])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][0]+w_list[i])
Max=0
for j in range(100001):
    if dp[n][j]<=W:
        if Max<=j:
            Max=j
print(Max)

Solution (Python):

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

dp = [[None for __ in range(N*max(V)+1)] for _ in range(N+1)]
dp[0] = [10**9 for _ in range(N*max(V)+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(N*max(V)+1):
        if V[i-1] >= v:
            dp[i][v] = min(dp[i-1][v], W[i-1])
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i-1]] + W[i-1])


print(max(i for i, w in enumerate(dp[-1]) if w <= M))

Solution (Python):
inf = 10 ** 9 + 1
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = {0: 0}
for w, v in wv:
    ndp = dp.copy()
    for dv, dw in dp.items():
        nw = w + dw
        if nw > W: continue
        nv = v + dv
        ndp.setdefault(nv, inf)
        if nw < ndp[nv]:
            ndp[nv] = nw
    dp = ndp
print(max(dp.keys()))

Solution (Python):
n, W = map(int, input().split())
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

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

Solution (Python):
import bisect
n,w_max=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") for i in range(10**5+1)] for j in range(n+1)]
DP[0][0]=1
for i in range(1,n+1):
  for j in range(i*(10**3)+1):
    if j>V[i-1]:
      DP[i][j]=min(DP[i-1][j],DP[i-1][j-V[i-1]]+W[i-1])
    else:
      DP[i][j]=min(DP[i-1][j],W[i-1])
ans=bisect.bisect_right(DP[n],w_max)-1
print(ans)

Solution (Python):



import numpy as np

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

dp = np.ones(N * int(1e4)) * int(1e10)
dp[0] = 0
for i in range(N):
    w, v = map(int, input().rstrip().split(' '))
    dp[v:] = np.min(np.vstack([dp[v:], dp[:-v] + w]), axis=0)
    
    
print(1 + np.where(dp[1:] <= W)[0][-1])

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

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

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

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

max_weight = W+1
max_cost = sum([v for w, v in wv])




dp = [INF for _ in range(max_cost+10)]
dp[0] = 0

for w, v in wv:
    
    
    for i in reversed(range(v, max_cost+1)):
        dp[i] = min(dp[i], dp[i-v]+w)


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

Solution (Python):
n,w=map(int,input().split())
dp=[0]*(n*10**3+1)
c,p=map(int,input().split())
dp[p]=c
mpos=p
for _ in range(n-1):
  c,p=map(int,input().split())
  for i in range(mpos+p,0,-1):
    if dp[i-p]!=0:
      if dp[i]==0:
        dp[i]=dp[i-p]+c
      else:
        dp[i]=min(dp[i-p]+c,dp[i])
  if dp[p]==0:
    dp[p]=c
  else:
    dp[p]=min(dp[p],c)
  mpos=mpos+p
ans=0
for i in range(len(dp)):
  if dp[i]<=w and dp[i]!=0:
    ans=i
print(ans)

Solution (Python):
import numpy as np
INF = 10 ** 12

N, W = map(int, input().split(" "))
wv = np.array([[int(i) for i in input().split(" ")] for _ in range(N)])

sumv = np.sum(wv[:,1])

dp = np.zeros((N + 1, sumv + 1), dtype=np.int64)
dp[0][1:] = INF

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

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

print(ans)

Solution (Python):
import numpy as np
INF = 10 ** 12

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

w = np.array(w, dtype=np.int64)
v = np.array(v, dtype=np.int64)
sumv = np.sum(v)


dp = np.zeros((N + 1, sumv + 1), dtype=np.int64)
dp[0][1:] = INF

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

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

print(ans)

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

dp = [[float("inf")] * (N * 10 ** 3 + 1) for _ in range(2)]
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

ans = 0
for i, w in enumerate(dp[N % 2 - 1]):
    if w <= W:
        ans = max(ans, i)
    else:
        break

print(ans)

Solution (Python):
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_e

E - Knapsack 2

value scatters less than weight does
"""
MAX_VALUE_SUM = 100000
DEFAULT_WEIGHT = 100000000007

def solve(wv_pairs):
    dp = [DEFAULT_WEIGHT] * (MAX_VALUE_SUM + 1)
    dp[0] = 0
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for vv in reversed(range(v_i, MAX_VALUE_SUM + 1)):
            dp[vv] = min(dp[vv], dp[vv - v_i] + w_i)
    return next(vv for vv in reversed(range(MAX_VALUE_SUM + 1)) if dp[vv] <= W)


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)

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

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

Solution (Python):
import numpy as np
N,W = map(int, input().split())
INF =  10**10
V_max = 100001
N_max = 101

dp = np.ones(V_max,dtype=np.int64)*INF
dp[0] = 0
for i in range(N):
    a = np.ones(V_max)*INF
    w,v = map(int,input().split())
    
    np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
ans = 0
for i,d in enumerate(dp):
    if d<=W:
        ans = i
print(ans)

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

dp = [[ 10**100 for i in range(sumv+1)] for j in range(N+1)]

dp[0][0] = 0

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

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

Solution (Python):
MAX_INT = int(10e10)

N,W = list(map(int,input().split()))
w = [0]
v = [0]

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
V_MAX = max(v)


dp = [[MAX_INT]*(N*V_MAX+1) for i in range(N+1)]

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

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

max_weight = W + 1
max_cost = sum([v for w,v in WV])
dp = [max_weight for _ in range(max_cost + 1)]

dp[0] = 0

for w,v in WV:
    for index in reversed(range(len(dp))):
        if dp[index] == max_weight:
            continue

        dp[index + v] = min(dp[index + v], dp[index] + w)


for cost in reversed(range(max_cost + 1)):
    if dp[cost]<=W:
        print(cost)
        break

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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Solution (Python):
n, w = map(int, input().split())
weight = []
value = []
INF = 10 ** 9


ans = 0

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

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

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

        else:
            dp[i + 1][j] = dp[i][j]


for i in sorted(range(sum(value) + 1), reverse = True):
        tmp = dp[n][i]
        if tmp <= w:
            print(i)
            exit()

Solution (Python):
import sys

input = sys.stdin.readline

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

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


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

for j in sorted(range(sum(v) + 1), reverse=True):
    t = dp[N][j]
    if t <= W:
        print(j)
        break

Solution (Python):
N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

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

Solution (Python):
import numpy as np

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

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

dp = np.full(n*10**3+1, np.inf)
dp[0] = 0

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

for i in range(n*10**3+1)[::-1]:
    if dp[i] <= ww:
        print(i)
        exit()

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

wv = [list(map(int, input().split())) for i in range(n)]
wv.sort(key=lambda x:x[1])
dp = {0:0}
for w, v in wv:
    dp_next = dp.copy()
    for key in dp:
        dp_next[key+v] = min(dp[key]+ w, dp.get(key+v, float("inf")))
    dp = dp_next
for key in sorted(dp.keys(), reverse=True):
    if dp[key] <= ww:
        print(key)
        exit()

Solution (Python):
import sys

n, w = map(int, sys.stdin.readline().split())
weight = []
value = []
sum_value = 0
for i in range(n):
    wi, vi = map(int, sys.stdin.readline().split())
    weight.append(wi)
    value.append(vi)
    sum_value += vi


wght = [1<<64] * (sum_value + 1)
wght[0] = 0
for i in range(n):
    for j in range(sum_value - value[i], -1, -1):
        wght[j + value[i]] = min(wght[j + value[i]], wght[j] + weight[i])
            
            


max_val = 0

for i in range(sum_value, -1, -1):
    if wght[i] <= w:
        
        max_val = max(max_val, i)

print(max_val)

Solution (Python):


import numpy as np

def main():
    N, W = map(int, input().split())

    dp = np.full((N+1, N * (10**3) +1), np.inf)
    dp[0][0] = 0

    for i in range(N):
        weight, value = map(int, input().split())

        dp[i+1][:value] = dp[i][:value]
        dp[i+1][value:] = np.minimum(dp[i][value:], dp[i][:-value] + weight)


    res = 0
    for i, weight in enumerate(dp[N]):
        if weight <= W: res = i

    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np


input = sys.stdin.readline


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

MAX_V = (10**3) * N +1

def knapsack(n, w):
    
    dp = np.full([N+1, MAX_V], np.inf)
    dp[0][0] = 0
    for i in range(n):
        w, v = map(int, input().split())
        dp[i+1] = dp[i]
        dp[i+1][v:] = np.minimum(dp[i][v:], dp[i][:-v] + w)
    print(np.max(np.where(dp <= W)))

knapsack(N, W)

Solution (Python):
import sys


input = sys.stdin.readline


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

MAX_V = (10**3) * N +1

f_inf = float('inf')

def knapsack(n, w):
    
    dp = [f_inf] * MAX_V
    
    dp[0] = 0
    sum_v = 0
    
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(MAX_V, v-1, -1):
            new_weight = dp[j - v] + w
            if new_weight > W:
                continue
            if dp[j] > new_weight:
                dp[j] = new_weight

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

knapsack(N, W)

Solution (Python):
N,W = map(int,input().split())
w,v = [],[]
dp = [[10**10]*100100 for _ in range(101)]
dp[0][0] = 0
for i in range(N):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
for i in range(N):
    for sum_v in range(100100):
        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 = 0
for i in range(100100):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):
def solve():
  N, W = map(int, input().split())
  INF = 1e9 + 5
  dp = [INF]  * (100001)
  dp[0] = 0
  items = []
  for i in range(N):
    w, v = map(int, input().split())
    items.append((w, v))

  sum_v = 0
  for w, v in items:
    sum_v += v
    temp_dp = list(dp) 
    for i in range(v, sum_v + 1):
      if temp_dp[i - v] != INF:
        dp[i] = min(temp_dp[i], temp_dp[i - v] + w)

  for i in range(100000, -1, -1):
    if dp[i] != INF and dp[i] <= W:
      print(i)
      break
      

if __name__ == "__main__":
  solve()

Solution (Python):
import sys

input = sys.stdin.readline


def nap(n, cap):
    mxk = 0
    inf = 10 ** 10
    wei = [0] + [inf] * 100000
    for _ in range(n):
        w, v = map(int, input().split())
        for vk in range(100000, v - 1, -1):
            nw = wei[vk - v] + w
            if nw > cap: continue
            if wei[vk] > nw:
                wei[vk] = nw
                if vk > mxk:
                    mxk = vk
    return mxk


n, cap = map(int, input().split())
print(nap(n, cap))

Solution (Python):
def solve():
    N, W = map(int, input().split())
    weight = [0 for i in range(N)]
    value = [0 for i in range(N)]
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    dp = [W + 1 for i in range(N * 1000 + 1)]
    dp[0] = 0
    V = 0

    for i in range(N):
        wi = weight[i]
        vi = value[i]
        for v in range(V, -1, -1):
            w = dp[v] + wi
            if dp[v + vi] <= w: continue
            dp[v + vi] = w
        V += vi

    for i in range(V, -1, -1):
      if dp[i] <= W: return i
    return 0

print(solve())

Solution (Python):
def main():
    N, W = [int(n) for n in input().split()]
    
    baggages = [[int(n) for n in input().split()] for i in range(N)]
    baggages.insert(0, [0, 0])

    VALUE, WEIGHT = 1, 0
    VALUE_LIMIT = int(1e5)
    INF = int(1e15)

    
    dp = [[-1] * (VALUE_LIMIT+1) for n in range(N+1)]
    
    dp[0] = [INF] * (VALUE_LIMIT+1)
    dp[0][0] = 0
    
    for baggage in range(1, N+1):
        for value in range(VALUE_LIMIT+1):
            if dp[baggage][value] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][value]
            val2 = (dp[baggage-1][value-bag_v] + bag_w) if value >= bag_v else INF
            dp[baggage][value] = min(val1, val2)
    
    max_val = 0
    for index, w in enumerate(dp[N]):
        if w <= W:
            max_val = index
    print(max_val)


if __name__ == "__main__":
    main()

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

dp = [{} for i in range(N+1)]
dp[0][0] = 0
for i,(w,v) in enumerate(wv):
    for v0,w0 in dp[i].items():
        if v0 in dp[i+1]:
            dp[i+1][v0] = min(dp[i+1][v0], w0)
        else:
            dp[i+1][v0] = w0
        if w0+w > W: continue
        if v0+v in dp[i+1]:
            dp[i+1][v0+v] = min(dp[i+1][v0+v], w0+w)
        else:
            dp[i+1][v0+v] = w0+w
print(max(dp[-1].keys()))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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())

n,w = li()
INF = float('inf')

dp = [[INF]*(n*1000+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
    
for i in range(1,n+1):
    wi, vi = li()
    for j in range(1, n*1000+1):
        if j-vi >= 0:
            dp[i][j] = min(dp[i][j],
                           dp[i-1][j],
                           dp[i-1][j-vi] + wi)
        else:
            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 = i
        
print(ans)

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

M = sum(v)

dp = [[W+1 for _ in range(M + 1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    dp[i+1][v[i]] = min(dp[i][v[i]], w[i])
    for j in range(v[i]):
        dp[i+1][j] = dp[i][j]
    for j in range(v[i], M + 1):
        dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i])
for i in range(M, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()

Solution (Python):
import sys
input=sys.stdin.readline
N,W=map(int,input().split())
max_v=10**5
DP=[0]+[float('inf')]*max_v 
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(max_v,v-1,-1):
        DP[i]=min(DP[i],DP[i-v]+w)
ans=0
for v,w in enumerate(DP):
    if w<=W:
        ans=v
print(ans)

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

max_total = 0
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    max_total += p[-1][1]
    
    
MAX_WEIGHT = 1000000009
dp = [[MAX_WEIGHT for i in range(max_total+1)] for j in range(N+1)]
dp[0][0]=0
i = 0
for w, v in p:
    i += 1
    for target_val in range(0, max_total+1):
        
        if target_val-v >=0 and dp[i-1][target_val] > (dp[i-1][target_val-v]+w):
            dp[i][target_val] = dp[i-1][target_val-v]+w
        else:
            dp[i][target_val] = dp[i-1][target_val]
            
ret = 0
for v, w in enumerate(dp[N]):
    if w<=W and v>ret:
        ret = v
print(ret)

Solution (Python):
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

dp = [0 for k in range(100001)]
used = [[0 for i in range(n)] for k in range(100001)]

for i in range(1,100001):
    mina = 1000000000000
    useda = [0 for i in range(n)]
    for k in range(n):
        if i-values[k] >= 0:
            if dp[i-values[k]] != -1 and used[i-values[k]][k] == 0 :
                
                if  dp[i-values[k]]+weighs[k]<mina:
                        
                        mina = dp[i-values[k]]+weighs[k]
                        useda = used[i-values[k]][:]
                        useda[k] = 1
                
    if mina == 1000000000000:
        dp[i] = -1
    else:
        dp[i] = mina
    used[i] = useda

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

print(ans)

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

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


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

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))

def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    E()