Problem:
0-1 Knapsack Problem You have N items that you want to put them into a knapsack. Item i has value v i and weight w i . You want to find a subset of items to put such that:  The total value of the items is as large as possible.  The items have combined weight at most W , that is capacity of the knapsack.  Find the maximum total value of items in the knapsack. Input  N  W  v 1  w 1  v 2  w 2 : v N  w N  The first line consists of the integers N and W . In the following lines, the value and weight of the i -th item are given. Output Print the maximum total values of the items in a line. Constraints  1 ≤ N ≤ 100  1 ≤ v i ≤ 1000  1 ≤ w i ≤ 1000  1 ≤ W ≤ 10000  Sample Input 1 4 5
4 2
5 2
2 1
8 3 Sample Output 1 13 Sample Input 2 2 20
5 9
4 10 Sample Output 2 9

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

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

weight = []
value = []
for _ in range(n):
    v, we = map(int, input().split())
    weight.append(we)
    value.append(v)







for i in range(n):
    for j in range(w+1):
        if j >= weight[i]:
            dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]




print(dp[n][w])

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

dp = [0]*(W+1)
L = []
for i in range(N):
    ta,tb = map(int,input().split())
    L.append([ta,tb])

for i in range(N):
    for w in range(W,-1,-1):
        if w-L[i][1]>=0 :dp[w] = max(dp[w],dp[w-L[i][1]]+L[i][0])
print(dp[-1])

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


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

for i in range(n):
    for sum_w in range(w + 1):
        
        if sum_w - W[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - W[i]] + V[i])
        
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])

Solution (Python):
N, W = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] 
for i in range(N):
  v, w = vw[i]
  for j in range(W+1):
    if w <= j:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
    else:
      dp[i+1][j] = dp[i][j]
print(dp[N][W])

Solution (Python):
N,W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    v,w = map(int,input().split())
    for j in range(1,W+1):
        if j-w >=0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

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

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

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

print(max(dp[N-1]))

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

def solve(p,w):
  if dp[p][w]:
    return dp[p][w]
  if p == N:
    dp[p][w]= 0
  elif w < VW[p][1]:
    dp[p][w] = solve(p+1,w)
  else:
    dp[p][w] = max(solve(p+1,w),solve(p+1,w-VW[p][1])+VW[p][0])
  return dp[p][w]

print(solve(0,W))

Solution (Python):
N, W = map(int, input().split())
vw = [map(int, input().split()) for _ in range(N)]
value, weight = [list(i) for i in zip(*vw)]
dp = [[0]*(W+1)]*(N+1)

dp = [[0]*(W+1) for _ in range(N+1)] 
for i in range(0,N):
    for w in range(W+1):
        
        
        if w >= weight[i]:
            dp[i + 1][w] = max(dp[i][w-weight[i]] + value[i] ,dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]

dpmax = 0
for i in range(len(dp)):
    for j in range(len(dp[0])):
        if dpmax < dp[i][j]:
            dpmax = dp[i][j]
print(dpmax)

Solution (Python):






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


dp = [[0 for w in range(W+5)] for i in range(N+5)] 








for i in range(N):
  for w in range(W+1): 
    if(w>=weight[i]):
        dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
    else:
        dp[i+1][w] = dp[i][w]


print(dp[N][W])

Solution (Python):
def main():
    n, w = map(int, input().split())
    v_list = []
    w_list = []
    for i in range(n):
        _v, _w = map(int, input().split())
        v_list.append(_v)
        w_list.append(_w)

    dp = [[0] * (w+1) for _ in range(n+1)]
    for i in range(n):
        for _w in range(1, w+1):
            
            if w_list[i] <= _w:
                dp[i+1][_w] = max(dp[i][_w], dp[i][_w - w_list[i]] + v_list[i])
            
            else:
                dp[i+1][_w] = dp[i][_w]

    print(dp[n][w])


main()

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



dp = [[0 for _ in range(0, W + 1)] for _i in range(N + 1)]

for i in range(N):
  for w in range(1, W + 1):
    if w >= weight[i]:
      dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + value[i])
    else:
      dp[i + 1][w] = dp[i][w]

print(dp[N][W])

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

def check():
    for w in range(W+1):
        dp[0][w] = 0
        G[0][w] = 'DIAGNOAL'
    for i in range(1, N+1):
        dp[i][0] = 0
    for i in range(1, N+1):
        for w in range(1, W+1):
            if I[i][1] <= w:
                if I[i][0]+dp[i-1][w-I[i][1]] > dp[i-1][w]:
                    dp[i][w] = dp[i-1][w-I[i][1]]+I[i][0]
                    G[i][w] = 'DIAGNOAL'
                else:
                    dp[i][w] = dp[i-1][w]
                    G[i][w] = 'TOP'
            else:
                dp[i][w] = dp[i-1][w]
                G[i][w] = 'TOP'
        max_value = max(dp[i])
    return max_value

print(check())

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

def main():
    N,W = map(int, readline().split())
    value = []; weight = []
    for _ in range(N):
        v, w = map(int, readline().split())
        value.append(v); weight.append(w)
    DP0 = [0] * (W+1)
    DP1 = [0] * (W+1)
    for i in range(N):
        for w in range(weight[i], W+1):
            DP1[w] = max(DP0[w], DP0[w-weight[i]]+value[i])
        DP0 = DP1.copy()
    print(max(DP0))


if __name__ == "__main__":
    main()

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

item_list = [list(map(int, input().split())) for i in range(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):
        if j - item_list[i][1] >= 0:
            dp[i + 1][j] = max([dp[i][j], dp[i][j - item_list[i][1]] + item_list[i][0]])
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[-1][-1])

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

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

for i in range(1,1+N):
    for j in range(10100):
        if j-W[i-1] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i-1]]+V[i-1])
        else:
            dp[i][j] = dp[i-1][j]
    
print(dp[N][WI])

Solution (Python):
import sys

N, W = map(int, sys.stdin.readline().strip().split())

weights = []
for _ in range(N):
    v, w = map(int, sys.stdin.readline().strip().split())
    weights.append((v, w))

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]


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


print(max(dp[N]))

Solution (Python):
N, W = map(int, input().split())
value = []
weight = []
for i in range(N):
    v, w = map(int, input().split())
    value.append(v)
    weight.append(w)
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for max_w in range(W + 1):
        if max_w >= weight[i]:
            dp[i + 1][max_w] = max(dp[i][max_w],
                                   dp[i][max_w - weight[i]] + value[i])
        else:
            dp[i + 1][max_w] = dp[i][max_w]
print(dp[N][W])

Solution (Python):
n,w = map(int,input().split())
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
vw = []
for i in range(n):
    vw.append(list(map(int,input().split())))
for i in range(1,n+1):
    vi = vw[i-1][0]
    wi = vw[i-1][1]
    for j in range(1,w+1):
        if wi <= j:
            dp[i][j] = max(dp[i-1][j-wi]+vi, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][w])

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

for i in range(n):
    for j in range(weight+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[-1][-1])

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


def knapsack(N, W, weight, value):
    
    inf = float('inf')
    dp = [[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i] = 0

    
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    return dp[N][W]


print(knapsack(N, W, ws, vs))

Solution (Python):
n, w = map(int, input().split())
vw = [[int(i) for i in input().split()] for _ in range(n)]
dp = [[-1 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][i] = 0
for i in range(n):
    for j in range(w + 1):
        if j >= vw[i][1]:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - vw[i][1]] + vw[i][0])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][w])

Solution (Python):
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


















def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    
    n, W_max = map(int, input().strip().split())
    lv = []
    lw = []
    for _ in range(n):
        a, b = map(int, input().strip().split())
        lv.append(a)
        lw.append(b)

    l_maxSumVal = [[-1 for _ in range(n+1)] for _ in range(W_max + 1) ]
    
    def calc_maxSumVal(i, W):
        if i > n-1: 
            return 0
        elif l_maxSumVal[W][i] != -1:
            return l_maxSumVal[W][i]
        elif W < lw[i]: 
            l_maxSumVal[W][i+1] = calc_maxSumVal(i + 1, W)
            return l_maxSumVal[W][i+1]
        else: 
            l_maxSumVal[W - lw[i]][i+1] = calc_maxSumVal(i + 1, W - lw[i]) 
            l_maxSumVal[W][i+1] = calc_maxSumVal(i+1, W)
            return max(lv[i] + l_maxSumVal[W - lw[i]][i+1], l_maxSumVal[W][i+1])
    
    
    print(calc_maxSumVal(0,W_max))

if __name__ == '__main__':
    main()

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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


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

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

Solution (Python):
n,W = map(int,input().split())
v = [];w = []
for j in range(n):
    a,b = map(int,input().split())
    v.append(a);w.append(b)

dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i],dp[i][j])
print(dp[-1][-1])

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

Solution (Python):
N,W = map(int,input().split())
v = [0]*N
w = [0]*N
for i in range(N): v[i],w[i] = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j - w[i] < 0: dp[i+1][j] = dp[i][j]
        else: dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[N][W])

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

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

DP = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    for w in range(W + 1):
        if w >= weight[i]:
            DP[i + 1][w] = max(DP[i][w - weight[i]] + value[i], DP[i][w])
        else:
            DP[i + 1][w] = DP[i][w]

print(DP[N][W])

Solution (Python):
N, W = map(int, input().split())
items = [[0, 0]]

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


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

for i in range(1, N + 1):
	for w in range(1, W + 1):
		
		if items[i][1] <= w:
			dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i][1]] + items[i][0])
		else:
			dp[i][w] = dp[i-1][w]

print(dp[N][-1])

Solution (Python):
n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]


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



for i in range(1, n + 1):
    for j in range(w + 1):
        if j - item[i - 1][1] >= 0:
            dp[i][j] = max(dp[i - 1][j - item[i - 1][1]] + item[i - 1][0], dp[i - 1][j])
            pass
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[n][w])

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

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

DP=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        item=VW[i]
        DP[i+1][j]=max(DP[i][j],DP[i+1][j])
        if 0<=j+item[1]<=w:
            DP[i+1][j+item[1]]=max(DP[i+1][j+item[1]],DP[i][j]+item[0])

print(DP[-1][-1])

Solution (Python):
n,m=map(int,input().split())
v=[0]*n
w=[0]*n
for i in range(n):
    v[i],w[i]=map(int,input().split())
dp=[0]*(m+1)
old=[0]*(m+1)
for i in range(n):
    for j in range(1,m+1):
        if j>=w[i]:
            dp[j]=max(old[j],old[j-w[i]]+v[i])
    old=dp.copy()
print(dp[m])

Solution (Python):
N, W = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in reversed(range(N)):
	for j in range(W + 1):
		if j < vw[i][1]:
			dp[i][j] = dp[i + 1][j]
		else:
			dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - vw[i][1]] + vw[i][0])

print(dp[0][W])

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

for i in range(N):
    for j in range(W+1):
        if(j >= V[i][1]):
            DP[i+1][j] = max(DP[i][j], DP[i][j-V[i][1]]+V[i][0])
        else:
            DP[i+1][j] = DP[i][j]
print(DP[N][W])

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

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

Solution (Python):
from pprint import pprint

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

dp = [ [0]*(W+1) for _ in range(n+1) ]
for i in range(n):
    for j in range(W+1):
        v = vw[i][0]
        w = vw[i][1]
        if w<=j:
            dp[i+1][j] = max( dp[i][j-w]+v, dp[i][j] )
        else:
            dp[i+1][j] = dp[i][j]

print( dp[n][W] )

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


dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for w in range(W+1):
        value, weight = vw[i]
        
        if w >= weight:
            dp[i+1][w] = max(dp[i][w], dp[i][w-weight] + value)
        
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Solution (Python):
n, m = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(n)]
V = [v for v, w in VW]
W = [w for v, w in VW]




DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(m+1):
        if j < W[i]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = max(DP[i][j], DP[i][j-W[i]]+V[i])
print(DP[n][m])

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

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

print(dp[N][W])

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

values = [0]
weights = [0]

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

dps = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if j >= weights[i]:
            dps[i][j] = max(dps[i - 1][j], dps[i - 1]
                            [j - weights[i]] + values[i])
        else:
            dps[i][j] = max(dps[i - 1][j], dps[i][j - 1])

print(dps[N][W])

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

dp=[[0 for _ in range(W+1)]  for _ in range(N+1)]

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

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

def resolve():
    N, W = map(int, input().split())
    vw = [list(map(int, input().split())) for _ in range(N)]

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

    for i in range(1, N+1):
        for j in range(0, W+1):
            v_i = vw[i-1][0]
            w_i = vw[i-1][1]
            if w_i<=j:
                dp[i][j] = max(dp[i-1][j-w_i]+v_i, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[N][W])

if __name__ == '__main__':
    resolve()

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


dp=[[0]*(w0+1) for _ in range(n+1)]

for i in reversed(range(n)):
	for j in range(w0+1):
		if j-w[i]<0:
			dp[i][j]=dp[i+1][j]
		else:
			dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][w0])

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

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

print(dp[N][W])

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

	dp = [0] * (W + 1)
	
	for item in items:
		v, w = item
		for i in reversed(range(W - w + 1)):
			if dp[i + w] < dp[i] + v:
				dp[i + w] = dp[i] + v
	print(max(dp))

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

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

for i in range(1, N+1):
  for w in range(1, W+1):
    if(w - weight[i] >= 0):
      dp[i][w] = max(dp[i-1][w-weight[i]]+value[i], dp[i-1][w])
    else:
      dp[i][w] = dp[i-1][w]

print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * 100100 for _ in range(N + 10)] 
for i in range(N):
    for j in range(W + 1):
        if j - vw[i][1] >= 0:
            dp[i + 1][j] =  max(dp[i][j - vw[i][1]] + vw[i][0], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[N][W])

Solution (Python):
import copy
n, w = map(int, input().split())
V = []
W = []
for i in range(n):
  vi, wi = map(int, input().split())
  V.append(vi)
  W.append(wi)
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):
    vi, wi = V[i], W[i]
    if j >= wi:
      dp[i+1][j] = max(dp[i][j - wi] + vi, dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[-1][-1])

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

values = []
weights = []

for i in range(N):
    v, w = list(map(int, input().split()))
    values.append(v)
    weights.append(w)

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

for i in range(1, N+1):
    for j in range(1, W+1):
        w = weights[i-1]
        v = values[i-1]

        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j- w] + v)
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][W])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,W=map(int,input().split())
    v,w=[0]*N,[0]*N
    for i in range(N):
        v[i],w[i]=map(int,input().split())
    dp=[[0]*2*10**5 for _ in range(N+1)]
    for i in range(N):
        for weight in range(W+1):
            dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight])
            if weight-w[i]>=0:
                dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight-w[i]]+v[i])
    print(dp[N][W])

if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())  
items = [list(map(int, input().split())) for _ in range(N)]  
dp = [[0]*(W+1) for _ in range(N+1)]  
dp[0][0] = 0  
for i in range(N):  
    for j in range(W+1):
        
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        
        if j + items[i][1] > W:
            continue
        dp[i+1][j+items[i][1]] = max(dp[i+1][j+items[i][1]], dp[i][j]+items[i][0])

ans = max(dp[N])
print(ans)

Solution (Python):
N, W = map(int, input().split())
v = [None] * N
w = [None] * N

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

dp = [[None for _ in range(W+1)] for _ in range(N+1)]




for j in range(W+1):
  dp[0][j] = 0


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

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    N, W = iip()
    dp = [0] * (W+1)

    for i in range(N):
        v, w = iip()
        for j in reversed(range(W+1)):
            id = j+w
            if id >= W+1:
                continue
            dp[id] = max(dp[id], dp[j]+v)

    print(dp[-1])











def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    if isinstance(l, list):
        l = l[0] 
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
N, W = map(int, input().split())
VW = [list(map(int, input().split())) for i in range(N)]
dp = [0] * (W + 1)
for i, (v, w) in enumerate(VW):
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)
print(dp[-1])

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

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

for i in range(N):
    v, w = map(int, input().split())
    for sum_w in range(W+1):
        if w <= sum_w:
            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w] + v)
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
v_w = [list(map(int, input().split())) for _ in range(N)]
dp = [([0]*(W+1)) for _ in range(N+1)]

for item in range(1, N+1):
    value = v_w[item-1][0]
    weight = v_w[item-1][1]
    for j in range(W+1):
        if j < weight:
            dp[item][j] = max(dp[item][j], dp[item-1][j])
        else:
            dp[item][j] = max(dp[item][j], dp[item-1][j], dp[item-1][j-weight]+value)

print(dp[N][W])