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 = list(map(int,input().split()))
w = []
v = []
for i in range(n):
    w_,v_ = list(map(int,input().split()))
    w.append(w_)
    v.append(v_)

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

print(dp[n][W])

Solution (Python):











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

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

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

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

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

dp=[0 for _ in range(W+1)]
for i in range(N):
	for w_ in range(W,w[i]-1,-1):
		dp[w_]=max(dp[w_],dp[w_-w[i]]+v[i])
print(dp[W])

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

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

Solution (Python):
import numpy as np

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

for _ in range(N):
    knap.append(tuple(map(int, input().split())))
    
dp = np.zeros((N+1, W+1), dtype=np.int64)

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

Solution (Python):


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

dp=[-1]*(W+1)
dp[0]=0

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

print(max(dp))

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 reversed(range(W+1)):
        if 0 <= j - w < W:
            dp[j] = max(dp[j-w] + v, dp[j])
print(max(dp))

Solution (Python):
def edu_dp_d_knapsack1():
    n, c = map(int, input().split())
    w, v = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0] * (c + 1) for _ in range(n)]
    dp[0][w[0]] = v[0]
    for i in range(1, n):
        for j in range(0, c + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
    print(max(dp[n - 1]))
edu_dp_d_knapsack1()

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

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

print(max(dp[-1]))

Solution (Python):
n,w=map(int,input().split()) 
wt=[] 
val=[] 
for i in range(n):
	x,y=map(int,input().split()) 
	val.append(y) 
	wt.append(x) 
dp=[[0 for j in range(w+1)] for i in range(n+1)] 
for i in range(n+1):
	for j in range(w+1):
		if i==0 or j==0:
			dp[i][j]=0 
		elif j>=wt[i-1]:
			dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-wt[i-1]]) 
		else:
			dp[i][j]=dp[i-1][j] 
print(dp[-1][-1])

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]*(w+1) for i 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):
import numpy as np
from numba import njit, i8


@njit(i8(i8, i8, i8[:], i8[:]), cache=True)
def solve(N, W, weights, values):
    dp = np.full((N + 1, W + 1), 0, dtype=np.int64)
    dp[0][0] = 0
    for i in range(N):
        for j in range(W + 1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            if j + weights[i] <= W:
                dp[i + 1][j + weights[i]] = max(
                    dp[i + 1][j + weights[i]], dp[i][j] + values[i]
                )
    return dp[-1].max()


N, W = map(int, input().split())
weights = np.zeros(N, dtype=np.int64)
values = np.zeros(N, dtype=np.int64)
for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
print(solve(N, W, weights, values))

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


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

for i in range(0, n):
    for j in range(w + 1):
        
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

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

Solution (Python):
import numpy as np
INF = 2**60 
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int64)
dp[0][0] = 0 
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W+1]))

Solution (Python):
import numpy as np
INF = 2**60 
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int64)
dp[0][0] = 0 
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W+1]))

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

Solution (Python):
n, w = list(map(int, raw_input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, raw_input().split()))
    weights.append(wi)
    values.append(vi)

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):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] if weights[i-1] <= j else 0)

print(dp[n][w])

Solution (Python):
n,w = map(int,input().split())
wait = [""]*n
value = [""]*n
for i in range(n):
    wait[i],value[i] = map(int,input().split())







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

for i in range(1,n+1):
    for j in range(0,w+1):
        
        if(j-wait[i-1]>= 0):
            knapsak[i][j] = max(knapsak[i-1][j],knapsak[i-1][j-wait[i-1]]+value[i-1])
            
        else:
            knapsak[i][j] = knapsak[i-1][j]
print(knapsak[n][w])

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

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

for i in range(0,n):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        p=0
        if j>=w :
            p=ans[i-1][j-w]+v
        ans[i][j]=max(ans[i-1][j],p)

print(ans[-1][W])

Solution (Python):
n,W=map(int,input().split())
values=[]
weights=[]

for _ in range(n):

    a,b=map(int,input().split())
    weights.append(a)
    values.append(b)

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

for i in range(0,n):
    for j in range(1,W+1):
        p=0
        if j>=weights[i] :
            p=ans[i-1][j-weights[i]]+values[i]
        ans[i][j]=max(ans[i-1][j],p)

print(ans[-1][W])

Solution (Python):


import numpy as np
import warnings
warnings.filterwarnings('ignore')

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])

Solution (Python):


import numpy as np
import warnings
warnings.filterwarnings('ignore')

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])

Solution (Python):
def num():
    x, y = map(int, input().split())
    dp = [0]*(y+1)

    for i in range(x):
        w, v = map(int, input().split())
        for j in range(y, w-1, -1):
            num = dp[j-w]+v
            if num > dp[j]:
                dp[j] = num
    print(dp[-1])

num()

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

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

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

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

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

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

print(dp[N][W])

Solution (Python):

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




dp = [[0]*100010 for _ in range(102)]


for i in range(102):
    for j in range(100010):
        dp[i][j] = 0



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

print(dp[N][W])

Solution (Python):
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

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

    print(dp[N][W])
main()

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

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


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


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 dp[i][j] < dp[i-1][j]:
      dp[i][j] = dp[i-1][j]
    if j >= w[i]:
      if dp[i][j] < dp[i-1][j-w[i]]+v[i]:
        dp[i][j] = dp[i-1][j-w[i]]+v[i]

print(dp[N][W])

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

print(solve())

Solution (Python):
import numpy as np

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

dp = np.zeros(W + 1, dtype = 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.max())

Solution (Python):
import numpy as np

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

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

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

print(dp.max())

Solution (Python):
import numpy as np

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

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

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

print(dp.max())

Solution (Python):
import numpy as np
N, W = map(int, input().split())

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

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
w = np.empty(N, dtype = np.int64)
v = np.empty(N, dtype = np.int64)
for i in range(N):
	w[i], v[i] = map(int, input().split())

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

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

print(dp.max())

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

dp = [0] * (W + 1)
dp[w[0]] = v[0]

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

Solution (Python):

"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

print(dp[n-1])
n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))
"""

n, W = [int(i) for i in input().split(' ')]

dp = [0]*(W+1)

for _ in range(n):
    curwt, val = [int(i) for i in input().split(' ')]
    for wt in range(W-curwt, -1, -1):
        dp[wt+curwt] = max(dp[wt+curwt], dp[wt]+val)

print(max(dp))

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

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

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


print(max(dp[-1]))

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


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-weight[i]]+value[i], dp[i][w])
		else:
			dp[i+1][w]=dp[i][w]
print(dp[-1][-1])


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




import numpy as np
N,W = map(int,input().split())
 
dp=np.zeros(W-1, dtype=np.int64)
for _ in range(N):
	w, v = map(int, input().split())



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

Solution (Python):
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  
    dp = [dp_min] * (W + 1)

    for item in range(N):
        S = range(W, weight_list[item] - 1, -1)
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[W]

import sys
input = sys.stdin.readline  

N, W = map(int, input().split())                                
 
price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)
 
print(knapsack_weight(single=True))

Solution (Python):
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = range(W, weight_list[item] - 1, -1)
        else:
            S = range(weight_list[item], W + 1)
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[W]

N, W = map(int, input().split())                                
 
price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)
 
print(knapsack_weight(single=True))

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


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

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

Solution (Python):
import numpy as np

n,wmax = 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((n+1, wmax+1))

for i in range(n):
  dp[i+1, :w[i]] = dp[i, :w[i]]
  dp[i+1, w[i]:] = np.maximum(dp[i, w[i]:], dp[i, :wmax-w[i]+1] + v[i])

print(int(dp.max()))

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

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

for i,[W,V] in enumerate(v):
    for j in range(w):
        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])

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

Solution (Python):
n,w=map(int,input().split())
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])
INF=float('inf')

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

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

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

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

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

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

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

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

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

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

print(max(dp[-1]))

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

Solution (Python):
n,w=map(int,input().split())
cost=[[0 for i in range(w+1)] for j in range(n+1)] 
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(1,n+1):
  for j in range(w+1):
    weight_=value[i-1][0] 
    value_=value[i-1][1] 
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(cost[n][w])

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



def ifvalid(i):
    if i<0:
        return False
    return True


def solve():
    n,W=sep()
    ar=[]
    for _ in range(n):
        ar.append(lis())
    dp=[[-1 for i in range(W+5)] for _ in range(n+5)]
    for j in range(0,ar[0][0]):
        dp[0][j]=0
    for j in range(ar[0][0],W+1):
        dp[0][j]=ar[0][1]
    for i in range(1,n):
        for w in range(W+1):
            if ifvalid(w-ar[i][0]):
                dp[i][w]=max(dp[i-1][w],dp[i-1][w-ar[i][0]]+ar[i][1])
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[n-1][W])








solve()

Solution (Python):
def knapsack(N,W,w,v):
    dp = [[0]*(W+1) for _ in range(N)]
    
    for i in range(N):
        for j in range(W+1):
            if j-w[i]>=0:
                dp[i][j] = max(dp[i-1][j],v[i]+ dp[i-1][j-w[i]])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[N-1][W]

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

print(knapsack(N,W,w,v))

Solution (Python):
def solve(ar_w,ar_v,n,w):
    dp = [[0] * (w+1) for _ in range(n+1)]

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


    print(dp[n][w])


if __name__ == '__main__':
    n,w = map(int,input().split())
    ar_w = [0]
    ar_v = [0]
    for i in range(n):
        a,b = map(int,input().split())
        ar_w.append(a)
        ar_v.append(b)

    solve(ar_w,ar_v,n,w)

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

	
    
	a,b=map(int,input().split())
	
	for j in range(1,w+1):
		dp1[j]=dp[j]
		if(a<=j):
			dp1[j]=max(dp1[j],dp[j-a]+b)
	
	dp=dp1.copy()
print(dp[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(w):
	dp[0][i]=0
for i in range(n):
	dp[i][0]=0
l=[]
for k in range(n):
	l.append(list(map(int,input().split())))

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

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

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

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

m = 0
for i in range(N + 1):
    m = max(m, max(dp[i]))

print(m)

Solution (Python):
import numpy as np

n,W=list(map(int,input().split()))

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

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

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

Solution (Python):
N, W = map(int, input().split())
w, v = [0], [0]
for i in range(N):
    w_i, v_i = map(int, input().split())
    w.append(w_i)
    v.append(v_i)
DP = [[0 for c in range(W+1)] for i in range(N+1)]
for i in range(1, N+1):
    for c in range(1, W+1):
        if c - w[i] < 0:
            DP[i][c] = DP[i-1][c]
        else:
            DP[i][c] = max(DP[i-1][c], DP[i-1][c-w[i]] + v[i])
print(DP[N][W])

Solution (Python):




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

w = [-1]
v = [-1]

memo = [[-1] * (tar_w + 1) for i in range(n + 1)]

for i in range(tar_w + 1):
    memo[0][i] = 0


def dp(n, tar_w):
    if memo[n][tar_w] == -1:
        if tar_w < w[n]:
            memo[n][tar_w] = dp(n - 1, tar_w)
        else:
            memo[n][tar_w] = max(dp(n - 1, tar_w), dp(n - 1, tar_w - w[n]) + v[n])
    return memo[n][tar_w]


for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)


ans = dp(n, tar_w)

print("{}".format(ans))

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