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())
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 j >= wv[i-1][0]:
      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[-1][-1])

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

dp = []
for i in range(n):
    dp.append([0]*(w+1))

for j in range(w+1):
    if j>=wts[0]:
        dp[0][j] = vals[0]

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

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

Solution (Python):
a = [int(x) for x in input().split()]
weight = a[1]
dp = [0] * weight + [0]
for x in range(a[0]):
    b = [int(x) for x in input().split()]
    for x in range(weight, b[0] - 1, -1):
        dp[x] = max(dp[x], dp[x - b[0]] + b[1])
print(dp[-1])

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

import numpy as np

dp = np.zeros(W + 1, dtype=int)

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

print(dp[-1])

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

import numpy as np

dp = np.zeros(W + 1, dtype=np.longlong)

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

print(dp[-1])

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

import numpy as np

dp = np.zeros(W + 1, dtype=np.longlong)

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

print(dp.max())

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

import numpy as np

dp = np.zeros(W + 1, dtype=int)

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

print(dp.max())

Solution (Python):
import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])


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

Solution (Python):
import numpy as np

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

dp = np.zeros(W+1, np.int64)

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

print(dp[-1])

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

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

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


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


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



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


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


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


from numba import njit
import numpy as np


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


@njit('(i8,i8,i8[:],i8[:])', cache=True)
def main(N, K, W, V):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    for i in range(N + 1):
        dp[i, 0] = 0

    for i in range(N):
        w, v = W[i], V[i]
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1, sum_w] = dp[i, sum_w]
            else:
                dp[i + 1, sum_w] = max(
                    dp[i, sum_w],
                    dp[i, sum_w - w] + v)
    print(dp[-1, -1])


main(N, K, W, V)

Solution (Python):
import numpy as np

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
  dp[w[i]:] = np.maximum(dp[:-w[i]]+v[i], dp[w[i]:])
print(dp[W])

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


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


def read_a_int():
    return int(read())


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


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

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

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

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

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

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

Solution (Python):
def main(N, W, P):
    dp = [[0]*(W + 1) for _ in range(N)]
    for j in range(P[0][0], W+1):
        dp[0][j] = P[0][1]

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

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

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

if __name__ == "__main__":
    N, W = map(int, input().split()) 
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, P)

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

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

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

print(dp[0][W])

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

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


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

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


print(max(dp[-1]))

Solution (Python):
n,W=map(int,input().split())
a=[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):
    weight,value=a[i]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=W:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

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


dp=[0]*(w+1)

for i in range(n):
    nextdp=[]
    x=[int(i) for i in input().split()]
    for j in range(w+1):
        if x[0] > j:
            nextdp.append(dp[j])
        else:
            nextdp.append(max(dp[j],dp[j-x[0]]+x[1]))
    dp=nextdp

print(max(dp))

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

Solution (Python):
n,w = list(map(int,input().split(' ')))
w_arr = [None]*(n+1)
v_arr = [None]*(n+1)
for i in range(1,n+1):
    w_arr[i],v_arr[i] = 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(w+1):
        if j-w_arr[i]>=0:
            dp[i][j] = max(dp[i-1][j-w_arr[i]] + v_arr[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
            
print(max(dp[-1]))

Solution (Python):
import math

n, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(n):
    weight, cost = map(int, input().split())
    for weight_already in range(W-weight, -1, -1):
        dp[weight_already+weight] = max(dp[weight_already+weight], dp[weight_already]+cost)
ans = max(dp)
print(ans)

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

print(int(dp.max()))

Solution (Python):
import math

n, w = map(int, input().split())
weights = []
costs = []
for i in range(n):
    a,b = map(int, input().split())
    weights.append(a)
    costs.append(b)
dp = [[0 for i in range(w+1)] for i in range(n)]
for i in range(w+1):
    if(i>= weights[0]):
        dp[0][i] = costs[0]

for i in range(1, n):
    for j in range(w+1):
        if(j >= weights[i]):
            val = max(dp[i-1][j], costs[i]+dp[i-1][j-weights[i]])
            dp[i][j] = val
        else:
            dp[i][j] =max(dp[i][j], dp[i-1][j])
print(dp[-1][-1])

Solution (Python):
import sys
 
input = sys.stdin.readline
 
 
def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))
 
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b
 
    ans = dp[-1][-1]
    print(ans)
 
 
if __name__ == "__main__":
    main()

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

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

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

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

print(dp[n][w])

Solution (Python):
import sys
import math
import itertools





def input():
    return sys.stdin.readline().rstrip()


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

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import itertools





def input():
    return sys.stdin.readline().rstrip()


def main():
    N, WW = map(int, input().split())
    W = []
    V = []
    for i in range(N):
        w, v = map(int, input().split())
        W.append(w)
        V.append(v)

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)
    
    
    dp = [[0] * (capacity + 1) for _ in range(item_count)]
    for item_i in range(item_count):
        for weight_i in range(1, capacity + 1):
            w = weights[item_i]
            if w <= weight_i:
                dp[item_i][weight_i] = max(
                    dp[item_i - 1][weight_i - w] + values[item_i],
                    dp[item_i - 1][weight_i])
            else:
                dp[item_i][weight_i] = dp[item_i - 1][weight_i]
    print(dp[item_count - 1][capacity])


if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())

dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, -1, - 1):
        v = dp[j] + v_list[i]
        if j + w_list[i] <= w and dp[j + w_list[i]] < v:
            dp[j + w_list[i]] = v
print(dp[-1])

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

INF = 10**18
    
def solve2():
  
  
  dp = [0] * (wmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    
    for w in range(wmax*i,-1,-1):
      if w-w1>=0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp[:W+1])
  
  
    
  return ret

ans = solve2()
  
print(ans)

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

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

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

if w[1] == 1:
    dp[1][1] = v[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):
from sys import stdin, stdout
import numba as nb 

@nb.njit()
def solve(n,w,weights, values):
	dp = [[0 for _ in range(w+1)] for k in range(n+1)]
	for i in range(1,n+1):
		for j in range(1,w+1):
			if weights[i] <= j:
				dp[i][j] = max(dp[i-1][j],
			   	dp[i-1][j-weights[i]] + values[i])
			else:
				dp[i][j] = dp[i-1][j]
	return dp[n][w]

def main():
	n, w = map(int,stdin.readline().split())
	values = []
	weights = []

	for _ in range(n):
		v,a = map(int, stdin.readline().split())
		values.append(a)
		weights.append(v)

	values = [0] + values
	weights = [0] + weights
	print(solve(n,w,weights,values))

if __name__ == "__main__":
	main()

Solution (Python):
import copy
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)
tmp_dp = [0] * (W+1)
for i in range(N):
    tmp_dp = copy.copy(dp)
    for j in range(W):
        if dp[j] != 0:
            if j + w[i] <= W:
                if dp[j + w[i]] < tmp_dp[j] + v[i]:
                    dp[j + w[i]] = tmp_dp[j] + v[i]
    if dp[w[i]] < v[i]:
        dp[w[i]] = v[i]
print(max(dp))

Solution (Python):
import sys

import numpy as np

input = sys.stdin.readline


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 = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i, (w_, v_) in enumerate(zip(w, v)):
        dp[i + 1] = dp[i]
        dp[i + 1, w_:] = np.maximum(dp[i, w_:], dp[i, :W + 1 - w_] + v_)

    ans = np.max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

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 j in range(n+1)]
for p in range(n):
  for q in range(w+1):
    if q<W[p]:
      DP[p+1][q]=DP[p][q]
    else:
      DP[p+1][q]=max(DP[p][q], DP[p][q-W[p]]+V[p])
print(DP[n][w])

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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    
    dpt = [0] * (W+1)
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            a = dpt[j]
            b = dpt[j-w]+v
            if a > b:
                dpt[j] = a
            else:
                dpt[j] = b
    
    print(dpt[W])

if __name__ == '__main__':
    main()

Solution (Python):


INF = float('inf')


def tc():
    n, cap = map(int, input().split())

    
    dp = [0] * (cap + 1)

    for i in range(n):
        w, v = map(int, input().split())
        for prev_w in reversed(range(cap - w + 1)):
            dp[prev_w + w] = max(dp[prev_w + w], dp[prev_w] + v)

    ans = max(dp)
    print(ans)


tc()

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






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

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

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

Solution (Python):
import sys
from copy import copy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, W = in_nn()
    wv = in_nl2(N)

    dp = [0] * (W + 1)

    for i in range(N):

        next_dp = copy(dp)
        for j in range(W):
            w, v = wv[i]
            if j + w <= W:
                next_dp[j + w] = max(next_dp[j + w], dp[j] + v)
            else:
                break
        dp = next_dp

    print(dp[W])


if __name__ == '__main__':
    main()

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

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


for w_i in range(1, w+1):
  dp[0][w_i] = float("-inf")
  
for w_i in range(w+1):
  for m_i in range(1, m+1):
    if w_i-WV[m_i-1][0]>=0:
      dp[m_i][w_i] = max(dp[m_i-1][w_i], dp[m_i-1][w_i-WV[m_i-1][0]]+WV[m_i-1][1])
    else:
      dp[m_i][w_i] = dp[m_i-1][w_i]

      
print(max(dp[-1]))

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

weight=[]
value=[]

for i in range(n):
    a,b=map(int,input().split())
    weight+=[a]
    value+=[b]

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

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

print(dp[n][w])

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

import numpy as np
 
dp = np.zeros(W + 1, dtype = int)

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

print(dp.max())

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

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

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

print(dp[N][W])

Solution (Python):
n,w=map(int,input().split())
wi=[]
vi=[]

for i in range(n):
  a,b=map(int,input().split())
  wi+=[a]
  vi+=[b]
  
dp=[[0]*(w+1) for i in range(n+1)]

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

Solution (Python):
n,w=map(int,input().split())
wi=[]
vi=[]

for i in range(n):
  a,b=map(int,input().split())
  wi+=[a]
  vi+=[b]
  
dp=[[0]*(w+1) for i in range(n+1)]

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

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

dp = [[0]*(w+8) for _ in range(n+10)]
weight = [0] * (n)
value = [0] * (n)

for i in range(n):
    weight[i] = li[i][0]
    value[i] = li[i][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, W = [int(i) for i in input().split()]
weight = [0]
value = [0]
for _ in range(N):
    temp1, temp2 = [int(i) for i in input().split()]
    weight.append(temp1)
    value.append(temp2)

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

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

print(dp[N][W])

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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

print(max(dp))

Solution (Python):
n,W=map(int,input().split())
wt,p=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    p.append(b)
dp=[0 for i in range(W+1)]
for x in range(1,n+1):
  
  for y in range(W,0,-1):
    if wt[x-1]<=y:
        
      dp[y]=max(dp[y-wt[x-1]]+p[x-1],dp[y])
    else:

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

Solution (Python):



n,W=map(int,input().split())
wt,p=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    p.append(b)
dp=[[0 for i in range(W+1)]for j in range(n+1)]
for x in range(1,n+1):
    for y in range(1,W+1):
        if wt[x-1]<=y:
            dp[x][y]=max(dp[x-1][y-wt[x-1]]+p[x-1],dp[x-1][y])
        else:
            dp[x][y]=dp[x-1][y]
print(dp[-1][-1])

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

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

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

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

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

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

Solution (Python):
n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif t[n][W]!=-1:
    return t[n][W]
  else:
    if w[n-1]<=W:
      t[n][W]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
      return t[n][W]
    else:
      t[n][W]=dp(n-1,W,w,p)
      return t[n][W]

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit))