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

def main():
    inf = 1<<29
    n,w = map(int,input().split())
    A = []
    for _ in range(n):
        a,b = map(int,input().split())
        A.append([a,b])
    dp = [0]*(w+1)
    for i in range(n):
        a = A[i][0]
        b = A[i][1]
        for j in range(w,b-1,-1):
            dp[j] = max(dp[j],dp[j-b]+a)
    res = 0
    for i in range(w+1):res = max(res,dp[i])
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, W = i_l()

values = []
weigth = []
for _ in range(N):
    v, w = i_l()
    values.append(v)
    weigth.append(w)

dp = [[0 for _ in range(10010)] for _ in range(110)]

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


print(dp[N][W])

Solution (Python):



if __name__ == "__main__":
    N, W = list(map(int, input().split()))
    bag = []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        bag.append((v, w))

    d = {}

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

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

    print(max(dp[N]))

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

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

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

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

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

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

if __name__ == "__main__":
    main()

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

V=[]
W=[]

for i in range(n):
	v,w=map(int,input().split())
	V.append(v)
	W.append(w)

DP=[[0]*(gw+1) for i in range(n+1)]

for i in range(n):
	for j in range(gw+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][gw])

Solution (Python):
import sys
sys.setrecursionlimit(15000)
n,w = map(int,sys.stdin.readline().split())
dp = [0]*(w+1)
for i in range(n):
  vi,wi = map(int,sys.stdin.readline().split())
  for j in range(w+1)[::-1]:
    if 0 <= j-wi and j-wi <= w:
      
      dp[j] = max(dp[j],dp[j-wi]+vi)
print(dp[-1])

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

N, W = na()
weight = [0] * 110
value = [0] * 110
for i in range(N):
    v, w = na()
    weight[i], value[i] = w, v
dp = [[0] * 10010 for _ in range(110)]
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):
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


N, W = inpl()
VW = [inpl() for _ in range(N)]

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

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


print(dp[N][W])

Solution (Python):






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

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


inf = float("inf")
dp = [[-inf for _ in range(W + 1)] for j in range(N + 1)]


for w in range(W):
    dp[0][w] = 0

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

print(dp[N][W])

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

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

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

VW = tuple(map(int, input().split()) for _ in range(N))

dp = [0] * (W + 1)
for v, w in VW:
    for i in reversed(range(w, W + 1)):
        dp[i] = max(dp[i], dp[i - w] + v)

ans = dp[W]
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,w =mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp=[0]*(w+1)
for v,ww in a:
    for i in range(ww,w+1)[::-1]:
        dp[i] = max(dp[i], dp[i-ww]+v)
print(dp[w])

Solution (Python):
n,lim = 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]*(lim+1) for _ in range(n+1)]
for i in range(n):
  for j in range(lim+1):
    if w[i] > j:
      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][lim])

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

for i in range(n):
    for j in range(w+1):
        if i==0 and vw[i][1]<=w:
            dp[i][0]=0
            dp[i][vw[i][1]]=vw[i][0]
            break
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])
        
        if not (0<=j-vw[i][1]<=w and dp[i-1][j-vw[i][1]]>=0):continue
        dp[i][j]=max(dp[i-1][j-vw[i][1]]+vw[i][0],dp[i][j])

print(max(dp[-1]))

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

Solution (Python):
n, w = map(int, input().split())
vw = [input().split() for _ in range(n)]
vw = [(int(x[0]), int(x[1]))for x in vw]

pdp = [0 for _ in range(w+1)]
cdp = [0 for _ in range(w+1)]

for i in range(n):
    for j in range(w):
        if j + vw[i][1] < w + 1:
            cdp[j + vw[i][1]] = max(pdp[j + vw[i][1]], pdp[j] + vw[i][0])
    pdp = cdp[:]
print(max(cdp))

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


print(dp[N][W])

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, W = na()
vw = nan(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 j - w < 0:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)

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(N):
    vi, wi = map(int, input().split())
    for w in range(W + 1):
        if wi <= w:
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w - wi] + vi)
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])

print(dp[N][W])

Solution (Python):








import sys
sys.setrecursionlimit(10 ** 5 + 10)


def resolve():
    N, W = map(int, input().split())
    value, weight = [0] * N, [0] * N
    for i in range(N):
        value[i],weight[i] = map(int, input().split())


    
    
    def knapsack(N, W, weight, value):
        dp = [[0] * (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], dp[i][w - weight[i]] + value[i])
                else:  
                    dp[i + 1][w] = dp[i][w]

        return dp[N][W]

    print(knapsack(N, W, weight, value))



resolve()

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

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

ans = 0

for i in range(W + 1):
    ans = max(ans, dp[i])

print(ans)

Solution (Python):


s = input().split()
N = int(s[0])
W = int(s[1])
values = []
weights = []

for n in range(N):
    s = input().split()
    values.append(int(s[0]))
    weights.append(int(s[1]))

max_value = [0 for i in range(W)]
contents = [[] for i in range(W)]

for i in range(W):
    if i == 0:
        buf = 0
    else:
        buf = max_value[i-1]
    for j in range(N):
        if i+1 < weights[j]:continue
        if i+1 == weights[j]:
            if buf < values[j]:
                contents[i] = [j]
                buf = values[j]
        if j in contents[i-weights[j]]:continue
        if buf < max_value[i-weights[j]]+values[j]:
            contents[i] = contents[i-weights[j]] + [j]
            buf = max_value[i-weights[j]]+values[j]
        
    if buf == max_value[i-1]:
        contents[i] = contents[i-1]
    max_value[i] = buf
    
print(max_value[W-1])

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


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

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


print(dp[n][w])

Solution (Python):
n, w = [int(i) for i in input().split()]
vw = [[int(i) for i in input().split()] for _ in range(n)]


dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    v_i, w_i = vw[i]
    for j in range(w+1):
        
        if j - w_i >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_i] + v_i)
        
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

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

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

v=[0]*N
w=[0]*N

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

nap=[[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):

    if j<w[i-1]:
      nap[i][j]=nap[i-1][j]
    else:
      nap[i][j]=max(nap[i-1][j],nap[i-1][j-w[i-1]]+v[i-1])


print(nap[N][W])

Solution (Python):
N, W = map(int, input().split())
w = [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):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j >= w[i][1]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i][1]] + w[i][0])

print(dp[N][W])

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

value, weight = [], []

for _ 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 j in range(W+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j - weight[i]] + value[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])

Solution (Python):
n,w1=map(int,input().split())
dp=[]
for i in range(n):
    temp=[]  
    for j in range(w1+1):
          temp.append(-1)
    dp.append(temp)

dp.append([0]*(w1+1))

w=[]
v=[]
for i in range(n):
  a,b=map(int,input().split())
  v.append(a)
  w.append(b)

for i in range(n-1,-1,-1):
  for j in range(w1+1):
    
    
    if j<w[i]:
      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][w1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,W = LI()
    g = LIR(n)
    dp = [0]*(W+1)
    for i in range(n):
        v,w = g[i]
        for j in range(W+1)[::-1]:
            nj = j+w
            if nj <= W:
                nd = dp[j]+v
                if dp[nj] < nd:
                    dp[nj] = nd
    print(dp[W])
    return


if __name__ == "__main__":
    solve()

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

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

dp = [[0]*(W+1) for _ in range(N+1)]
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+w[i] <= W:
            dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j]+v[i])

print(dp[N][W])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians

from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, W = MAP()
    VW = [LIST() for i in range(N)]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for i in range(N)]


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

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

Solution (Python):
from functools import lru_cache

N, W = [int(x) for x in input().split()]
VW = [[int(x) for x in input().split()] for _ in range(N)]

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

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

print(dp[N][W])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()

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

print(dp[W])

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

Solution (Python):
def  main():
    N,W = map(int,input().split(" "))
    V = []
    dp = [0 for _ in range(W+1)]
    for _ in range(N):
        V.append(tuple(map(int,input().split(" "))))
    V =  tuple(V)
    for i in range(N):
        tmp = list(dp)
        v,w = V[i]
        for j in range(W+1):
            if 0 <= j+w <= W:
                tmp[j+w] = max(dp[j+w],dp[j]+v)
        dp = list(tmp)
    print(dp[-1])
if __name__ == "__main__":
    main()

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):
def dp_all(dp):
  length = len(dp)
  for i in range(length):
    print(dp[i])

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

v = []
w = []

for i in range(N):
  v_dash,w_dash = map(int,input().split())
  v.append(v_dash)
  w.append(w_dash)

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

for i in range(N):
  for j in range(W+1):
    if w[i] > j:
      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())
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())
VW = [list(map(int,input().split())) for _ in range(N)]
Val = [VW[i][0] for i in range(N)]
Wei = [VW[i][1] for i in range(N)]

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


for n in range(1,N+1):
    for w in range(W+1):
        if w - Wei[n-1] >= 0:
            dp[n][w] = max(dp[n-1][w],dp[n-1][w-Wei[n-1]]+Val[n-1])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[n][w])

Solution (Python):
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

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

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

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

dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n):
    vi, wi = a[i]
    for j in range(w+1):
        if j + wi <= w:
            dp[i+1][j+wi] = max(dp[i][j]+vi, dp[i+1][j+wi])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print(max(dp[i+1]))

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

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

print (dp[N][W])

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

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] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

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

Solution (Python):

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


dp = [[0 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 >= vw[i][1]:
            dp[i+1][w] = max(dp[i][w-vw[i][1]] + vw[i][0], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]


print(dp[N][W])

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

d = [[0 for i in range(W + 1)]]

for i in range(0, N):
    d.append([])
    v_i, w_i = map(int, input().split())
    for k in range(0, W + 1):
        if k >= w_i:
            d[i + 1].append(max(d[i][k - w_i] + v_i, d[i][k]))
        else:
            d[i + 1].append(d[i][k])
            
print(max(d[N]))

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

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

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

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


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



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

Solution (Python):
from collections import namedtuple
from functools import lru_cache

Item = namedtuple('Item', ('v', 'w'))


class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    @lru_cache(maxsize=None)
    def dfs(self, w, index):
        item = items[index]
        if index == self.N - 1:
            if w + item.w <= self.W:
                return item.v
            else:
                return 0

        if w + item.w <= self.W:
            return max([
                
                self.dfs(w, index + 1),
                
                item.v + self.dfs(w+item.w, index + 1)
            ])
        else:
            
            return self.dfs(w, index + 1)

    def solve(self):
        
        return self.dfs(0, 0)


if __name__ == "__main__":
    N, W = list(map(int, input().split()))
    items = []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        items.append(Item(v=v, w=w))

    s = Solver(N, W, items)
    print(s.solve())

Solution (Python):
from collections import namedtuple

Item = namedtuple('Item', 'value, weight')


def make_knapsack_resolver(num_items, max_capacity):
    dp = [[0] * (max_capacity + 1) for _ in range(num_items + 1)]
    items = [Item(*[int(x) for x in input().split()]) for _ in range(num_items)]

    def resolve():
        calc_recurrence()
        return dp[0][max_capacity]

    def calc_recurrence():
        for idx_item in range(num_items - 1, 0 - 1, -1):
            for remaining_capacity in range(1, max_capacity + 1):
                if remaining_capacity < items[idx_item].weight:
                    dp[idx_item][remaining_capacity] = dp[idx_item + 1][remaining_capacity]
                else:
                    dp[idx_item][remaining_capacity] = max(
                        dp[idx_item + 1][remaining_capacity],
                        dp[idx_item + 1][remaining_capacity - items[idx_item].weight] + items[idx_item].value
                    )

    return resolve()


if __name__ == '__main__':
    N, W = list(map(int, input().split()))
    resolver = make_knapsack_resolver(N, W)
    print(resolver)

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

vw = []
for i in range(N):
    vw.append([int(i) for i in input().split(" ")])
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

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

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

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

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

Solution (Python):


n,w = map(int ,input().split())
dp = [[0] * (w+1)  for _ in range(n)]
ll = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(w+1):
        tmp_w = ll[i][1] + j
        if tmp_w <= w:
            dp[i][tmp_w] = max(dp[i][tmp_w], dp[i-1][j] + ll[i][0])
        dp[i][j] = max(dp[i][j], dp[i-1][j])
print(max(dp[n-1]))

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

dp = [[0 for _ in range(W + 10)] for _ in range(N + 10)]
value, weight = [], []
for _ in range(N):
    v, w = list(map(int, input().split()))
    value.append(v)
    weight.append(w)

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

print(dp[N][W])

Solution (Python):
N,W = [int(i) for i in input().split()]
data = [[int(i) for i in input().split()] for j 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 >= data[i][1]:
            DP[i+1][j] = (max(DP[i][j-data[i][1]]+data[i][0],DP[i][j]))
        else:
            DP[i+1][j] = DP[i][j]
            
print(DP[-1][-1])

Solution (Python):
"""
DP
"""
N, W = list(map(int, input().split()))
V = []
WEI = []

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


DP = []
for i in range(N+1):
    a = [None] * (W+1)
    DP.append(a)

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


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

print(DP[0][W])

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

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

for i in range(1,N+1):
   for j in range(W+1):
      if j >= w[i-1]:
         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][W])

Solution (Python):
from functools import lru_cache


@lru_cache(None)
def dp(i, cur):
    if cur > W:
        return float('-inf')
    elif i < 0:
        return 0
    else:
        v, w = VW[i]
        return max(dp(i - 1, cur), dp(i - 1, cur + w) + v)


N, W = map(int, input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
print(dp(N - 1, 0))