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^5  1 \leq w_i \leq W  1 \leq v_i \leq 10^9         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 5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000      Sample Output 2 5000000000  The answer may not fit into a 32-bit integer type.       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())
item=[]
for i in range(n):
    tmp=list(map(int,input().split()))
    item.append(tmp)

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

Solution (Python):

S=list(map(int,input().split()))
N=S[0]
W=S[1]

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

for i in range(N):
    w,v=map(int, input().split())
    for j in range(W+1):
        if(j>=w):
            C[i+1][j]=max(C[i][j],C[i][j-w]+v)
        else:
            C[i+1][j]=C[i][j]
print(C[N][W])

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

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

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

for i in range(N):
    for sum_w in range(W+1):
        
        if (sum_w-w[i])>=0:
            m=0

            m=dp[i][sum_w - w[i]]+v[i]

            dp[i+1][sum_w]=max(dp[i+1][sum_w],m)
        
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])

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

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

    WV = []
    for _ in range(N):
        WV.append(tuple(map(int, input().split())))

    

    return N, W, WV


def solve(N, W, WV):
    x, y = N + 1, W + 1
    DP = [[0 for _ in range(y)] for _ in range(x)]

    for i in range(N):
        weight = WV[i][0]
        for w in range(W + 1):
            
            if w + weight <= W:
                tw = w + weight
                DP[i + 1][tw] = max(DP[i + 1][tw], DP[i][w] + WV[i][1])

            
            DP[i + 1][w] = max(DP[i + 1][w], DP[i][w] + 0)

    
    
    return max(DP[-1])


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Solution (Python):
import copy
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [0 for m in range(M + 1)]
for n in range(N):
    f_ = copy.copy(f)
    for m in range(M + 1):
        if m >= W[n]:
            f_[m] = max(f[m], f[m - W[n]] + V[n])
    f = f_
print(f[M])

Solution (Python):
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [[0 for m in range(M + 1)] for n in range(N + 1)]
for n in range(N):
    for m in range(M + 1):
        if m < W[n]:
            f[n + 1][m] = f[n][m]
        else:
            f[n + 1][m] = max(f[n][m], f[n][m - W[n]] + V[n])
print(f[N][M])

Solution (Python):
n, w = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
dp = [[0] * 100001 for i in range(101)]

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

    dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[n][w])

Solution (Python):


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

import numpy as np

ndp = np.zeros(W + 1, dtype=np.int64)



for w, v in zip(w, v):
    
    
    np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])


print(ndp[-1])

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

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

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

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

    print(max(dp[N]))

if __name__ == '__main__':
    resolve()

Solution (Python):
N, W = map(int, input().split())
w = {}
v = {}

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

dp = {}
dp[0] = {}

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

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

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

dp = {}
dp[0] = {}

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

for i in range(1, N+1):
    dp[i] = {}
    for j in range(0,W+1):
        if j >= w[i]:
            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())
data=[]
for i in range(n):
    u,v=map(int,input().split())
    data.append((u,v))
can_pack=[[0 for i in range(w+1)] for j in range(n+1)]


for   i in range(n):
    a,b=data[i][0],data[i][1]
    
    for j in range(1,w+1):
        if    j>=a:
            can_pack[i+1][j]=max(can_pack[i][j-a]+b,can_pack[i][j])
        else:
            can_pack[i+1][j]=can_pack[i][j]
ans=0
for i in range(w+1):
    ans=max(ans,can_pack[n][i])
print(ans)

Solution (Python):
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = []
for i in range(N):
    wv.append([int(x) for x in stdin.readline().rstrip().split()])
wv.append([0,0])

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

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

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

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

N,W = imn()
wv = [iln() for _ 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):
        if w - wv[i][0] >= 0: dp[i+1][w] = max(dp[i+1][wv[i][0]], dp[i][w-wv[i][0]]+wv[i][1])
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])

Solution (Python):
n ,c = map(int,input().split())
wt =[]; val=[]

for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  

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

for w in range(c+1):
  wi = wt[0]
  if wi<=w:
    dp[0][w]=val[0]
  else:
    dp[0][0]=0

for i in range(1,n):
  wi = wt[i];vi = val[i]
  for w in range(1,c+1):
    if wi<=w:
      dp[i][w] = max(vi+dp[i-1][w-wi] , dp[i-1][w])
    else:
      dp[i][w] = dp[i-1][w]

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

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

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

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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.zeros(W+1, dtype=int)


for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
print(DP[-1])

Solution (Python):
n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    

for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

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

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


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


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,w = get_nums_l()
ppp = list(map(lambda s: tuple(map(int,s.strip().split())), sys.stdin.readlines()))


dp = [0] * (w+1)

for p in ppp:
    we = p[0]
    va = p[1]
    for i in reversed(range(len(dp))):
        if i+we > w:
            continue
        ne = i+we
        dp[ne] = max(dp[ne], dp[i]+va)



print(max(dp))

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

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

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] >= 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][W])

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

def main():
    n, w = map(int, input().split())

    dp = [0] * (w + 1)

    for _ in range(n):
        wi, vi = map(int, input().split())

        for wj in range(w, wi - 1, -1):
            nv = dp[wj - wi] + vi
            if dp[wj] < nv:
                dp[wj] = nv

    print(max(dp))

main()

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

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



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




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

print(dp[0][w])

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

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

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

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

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

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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1)
for i in range(N):
  w, v = map(int, input().split())
  dp[w:] = np.maximum(dp[:-w]+v, dp[w:])
print(int(dp[-1]))

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

for i in range(N):
    w,v = map(int, input().split())
    dp[i+1][:] = dp[i][:]
    for j in range(W):
        if dp[i][j] == -INF:continue 
        if j + w > W: continue
        dp[i+1][j+w] = max(dp[i][j+w], dp[i][j] + v)

print(max(dp[N]))

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

K = [[0 for x in range(W+1)] for y in range(N+1)]

for i in range(N+1):
	for w in range(W+1):
		if i == 0 or w == 0:
			K[i][w] = 0
		elif wt[i-1] <= w:

			K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])
		else:
			K[i][w] = K[i-1][w]
print(K[N][W])

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

from collections import Counter

dp = Counter()
dp[0] = 0
for w, v in WV:
  ndp = Counter()
  for k in dp:
   	ndp[k] = max(dp[k], ndp[k])
   	if k+w <= W:
   	 	ndp[k+w] = max(dp[k] + v, ndp[k+w])
  dp = ndp
print(dp.most_common()[0][1])

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


def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]

    dp = [0] * (w+1)
    for i in range(n):
        for j in range(w, wv[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j-wv[i][0]] + wv[i][1])
    print(max(dp))


if __name__ == "__main__":
    main()

Solution (Python):
INF = float('inf')
MAX_N = 110
MAX_W = 10**5 + 100

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

dp = [[0]*MAX_W for _ in range(MAX_N)]

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

        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])

Solution (Python):


import sys
input = sys.stdin.readline

def main():
    
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [[0]*(W+1) for i in range(N+1)]

    
    
    

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

    
    print(dp[N][W])

if __name__ == '__main__':
    main()

Solution (Python):
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考
"""

import sys
input = sys.stdin.readline

def main():
    
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    

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

    
    print(max(dp))

if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
wv = []

dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])

print(int(dp[-1]))

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

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

Solution (Python):
def main():
  import sys
  num,capacity=map(int,input().split())
  items=tuple([list(map(int,sys.stdin.readline().split())) for _ in range(num)])
  DP=[-1]*(capacity+1)
  DP[0]=0
  for item in items:
    weight=item[0]
    value=item[1]
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print(max(DP))
      
if __name__=="__main__":
  main()

Solution (Python):
def main():
  from collections import deque
  n,w=map(int,input().split())
  item=deque([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):
    itemNow=item.popleft()
    weight=itemNow[0]
    value=itemNow[1]
    for j in range(w+1):
      if j<weight:
        DP[i][j]=DP[i-1][j]
      else:
        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)
        
  print(DP[n][w])
      
if __name__=="__main__":
  main()

Solution (Python):
def main():
  
  n,w=map(int,input().split())
  item=[[0,0]]+[list(map(int,input().split())) for _ in range(n)]
  DP=[[0]*(w+1) for _ in range(n+1)]
  for i in range(n+1):
    weight=item[i][0]
    value=item[i][1]
    for j in range(w+1):
      if j<weight:
        DP[i][j]=DP[i-1][j]
      else:
        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)
        
  print(DP[n][w])
      
if __name__=="__main__":
  main()

Solution (Python):

























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


if __name__ == '__main__':
    main()

"""
in
4 5
2 3
1 2
3 4
2 2

out
7
"""

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n,w=mii()
wei,val=[0],[0]

for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

dp = [[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 >= wei[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wei[i]]+val[i])
        else:
            dp[i][j] = dp[i-1][j]

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n,w=mii()
wei,val=[0],[0]

for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

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>=wei[i]:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i])
        else:
            dp[i][j] = dp[i-1][j]

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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,w=map(int,input().split())
WV=[tuple(map(int,input().split())) for i in range(n)]
dp=[0]*(w+1)
for i in range(n):
  wi,vi=WV[i]
  for di in range(w,-1,-1):
    if not (0<=di-wi<10**7+10): continue
    dp[di]=max(dp[di],dp[di-wi]+vi)
print(dp[w])

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

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

dp=[0 for i in range(w+1)]
for q in range(n):
    bq=q
    for i in range(w):
        bi=w-i-1
        if bi+W[bq]<=w:
            dp[bi+W[bq]]=max(dp[bi]+V[bq],dp[bi+W[bq]])
    

print(dp[-1])

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

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

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])

Solution (Python):

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

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

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

table = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for i in range(n+1)]

def choice_max(a, b):
    if a > b:
        return a
    else:
        return b

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

print(dp[n][w])

Solution (Python):
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

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

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

print(DP[M][W])

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

dp = [0]*(w+1)

for _ in range(n):
  wei, v = map(int, input().split())
  dp_1 = dp[:]
  for j in range(w + 1):
    if j - wei >= 0:
      dp[j] = dp_1[j-wei] + v if (dp_1[j-wei] + v) > dp_1[j] else dp[j]
  
print(dp[w])

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

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

ab = []
for _ in range(n):
    a, b= (int(x) for x in input().split())
    ab.append([a, b])

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

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

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

def do_dp():
  for i,thing in enumerate(things):
    dp_1 = dp[i-1]
    for j in range(1, w + 1):      
      dp[i][j] = dp_1[j-thing[0]] + thing[1]  if (j - thing[0]) >= 0 else dp_1[j]
      dp[i][j] = max(dp[i][j], dp_1[j])

do_dp()
print(dp[n][w])

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): 
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(W+1):
        dp[N][i] = 0
    for i in reversed(range(N)):
        for j in range(W+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][W])
if __name__ == "__main__":
    main()

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


if __name__ == "__main__":
    resolve()

Solution (Python):


N, W = map(int, input().split())
knapsack_list = []
for i in range(N):
    knap =  list(map(int, input().split()))
    knapsack_list.append(knap)

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


for knap in knapsack_list:
    weight = knap[0]
    value = knap[1]
    for i in reversed(range(0, W+1)): 
        loc = i - weight
        if loc<0:
            break
        new_cost = cost_list[loc] + value
        new_cost = max(cost_list[i], new_cost)
        cost_list[i] = new_cost


for cost in cost_list:
    if cost > max_cost:
        max_cost = cost


print(max_cost)

Solution (Python):
def resolve():
    N, W = map(int, input().split())    
    w_v = [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):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w:
                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])
 
if __name__ == "__main__":
    resolve()