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

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

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

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

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

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

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

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

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

                    
print(DP[N][W])

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

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

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

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

print(dp[N][W])

Solution (Python):



n, w = map(int, input().split())
vw_l = [[int(x) for x in input().split()] for y in range(n)]

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

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

print(dp[n][w])

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

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

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

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

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

dp = [0] * (W+1)

value = []
weight = []

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

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

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

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

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


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

print(dp[N][W])

Solution (Python):
def main():
    _, W, *C = map(int, open(0).read().split())
    dp = [0]*(W+1)
    for v, w in zip(*[iter(C)]*2):
        for i in range(W-w, -1, -1):
            d_new = dp[i]+v
            if dp[i+w] < d_new:
                dp[i+w] = d_new
    print(max(dp))

if __name__ == '__main__':
    main()

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

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

print(dp[N][W])

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, WM = map(int, input().split())
V = [0] * N
W = [0] * N

for i in range(N):
    V[i], W[i] = map(int, input().split())
dp = [0] * (WM + 1)

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

Solution (Python):
N, W = map(int, input().split())
dp = [-1]*(W+1)
dp[0] = 0


for _ in range(N):
    value, weight = map(int, input().split())
    for i in range(W, weight-1, -1):
        if dp[i-weight] == -1:
            continue
        dp[i] = max(dp[i], dp[i-weight]+value)

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

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

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

print(dp[N][W])

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


dp=[[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i]=0

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

print(dp[N][W])

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

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

    for _ in range(N):
        v, w = map(int, readline().rstrip().split())
        for i in range(W, w-1, -1):
            dp[i] = max(dp[i], dp[i-w] + v)

    print(max(dp))

if __name__ == '__main__':
    main()

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

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

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

print(dp[N][W])

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

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



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

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

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

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

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

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

        if j + w <= W:
            dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)

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

print(dp[N][W])

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

vaw = [0 for i in range(W+1)]
for i in range(len(v)):
    for k in range(len(vaw)):
        j = len(vaw) - k - 1
        if vaw[j] != 0 and j+w[i]<=W:
            vaw[j+w[i]] = max(vaw[j+w[i]], vaw[j]+v[i])

    vaw[w[i]] = max(vaw[w[i]], v[i])

print(max(vaw))

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

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

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

print(dp[N][W])

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

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

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

Solution (Python):
def solve(N,W,knap):
    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):
            if dp[i-1][j]>-1:
                dp[i][j]=dp[i-1][j]
            if j-knap[i][1]>=0:
                if dp[i-1][j-knap[i][1]]>-1:
                    dp[i][j]=max(dp[i][j],dp[i-1][j-knap[i][1]]+knap[i][0])
    return max(dp[N])

N,W=map(int,input().split())
knap=[(0,0)]+[tuple(map(int,input().split())) for _ in range(N)]
print(solve(N,W,knap))

Solution (Python):
def main():
    N, W = map(int, input().split())
    
    item = [tuple(map(int, input().split())) for _ in range(N)]
    """
    使い回さない方
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for w in range(W+1):
            if w >= item[i][1]:
                dp[i+1][w] = max(dp[i][w], dp[i][w-item[i][1]]+item[i][0])
            else:
                dp[i+1][w] = dp[i][w]
    print(max(dp[N]))
    """
    """ 使い回す方 """
    dp = [0]*(W+1)
    for i in range(N):
        for w in range(W, -1, -1):
            if item[i][1] <= w:
                dp[w] = max(dp[w], dp[w-item[i][1]]+item[i][0])
    print(max(dp))


if __name__ == "__main__":
    main()

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

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


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

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

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

for i in range(n):
	tmpv, tmpw = map(int, input().split())
	for j in range(1, targetw+1):
		if j >= tmpw:
			dp[i+1][j] = max(dp[i][j-tmpw]+tmpv, dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]

print(dp[n][targetw])

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


dp = [0] * (W + 1)

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

print(dp[W])

Solution (Python):
def solve(N, W, vals, weights):
    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if weights[i] <= w:
                dp[i + 1][w] = max(dp[i][w - weights[i]] + vals[i], dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]
    print(dp[N][W])

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

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

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

for i in range(n):
    for j in range(w+1):
        if memo[i][j] > -1 and j+items[i][1] <= w:
            memo[i+1][j+items[i][1]] = max(memo[i+1][j+items[i][1]], memo[i][j]+items[i][0])
        memo[i+1][j] = max(memo[i+1][j], memo[i][j])

print(max(memo[-1]))

Solution (Python):



import sys

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

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


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


for n in range(N):
    for c in range(C + 1):
        dp[n + 1][c] = max(dp[n + 1][c], dp[n][c])

        if c + w[n] <= C:
            dp[n + 1][c + w[n]] = max(dp[n][c] + v[n], dp[n + 1][c + w[n]])




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

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

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

Solution (Python):
def main():
    import sys
    N, W = map(int, sys.stdin.readline().split())
    L = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    
    dp = [[0 for i in range(W+1)] for j in range(N)]
    
    dp[0][L[0][1]] = L[0][0]
    for i in range(1, N):
        dp[i] = dp[i-1].copy() 
        v, w = L[i][0], L[i][1]
        dp[i][w] = max(dp[i][w], v) 
        for j in range(W+1): 
            if dp[i-1][j] !=0 and j+w<=W:
                dp[i][j+w] = max(dp[i-1][j]+v, dp[i-1][j+w]) 
    print(max(dp[-1]))


if __name__=='__main__':
    main()

Solution (Python):







def main():
    n, w_limit = map(int, input().split())
    v, w = [0], [0]
    for _ in range(n):
        vi, wi = map(int, input().split())
        v.append(vi)
        w.append(wi)

    print(napzac(v, w, w_limit))


def napzac(v, w, w_limit):
    n = len(v)
    dp = [[0] * (w_limit + 1) for _ in range(n + 1)]  

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


if __name__ == '__main__':
    main()

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

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

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

print(dp[n][w])

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


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

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

print(dp[N][W])

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

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

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

Solution (Python):
import sys

N, W = [int(i) for i in sys.stdin.readline().rstrip("\n").split()]
goods_v = []
goods_w = []
for _ in range(N):
    elem = [int(i) for i in sys.stdin.readline().rstrip("\n").split()]
    goods_v.append(elem[0])
    goods_w.append(elem[1])
    
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if w >= goods_w[i]:
            dp[i+1][w] = max(dp[i][w], dp[i][w-goods_w[i]] + goods_v[i])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

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

Solution (Python):
def main():
    N,W = [int(x) for x in input().split()]
    vl,wl = [],[]
    for _ in range(N):
        v,w = [int(x) for x in input().split()]
        vl.append(v)
        wl.append(w)

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

    for i in range(N):
        for j in range(W+1):
            
            if j < wl[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j-wl[i]]+vl[i])
            
    print(int(dp[N][W]))


if __name__ == '__main__':
    main()

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




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


for i, (v, w) in enumerate(items):
    for j in range(MAX_W + 1):  
        
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

        
        if j + w <= MAX_W:
            
            dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)



print(dp[N][MAX_W])

Solution (Python):
nn,ww=map(int,input().split())
value=[0]*nn
weight=[0]*nn
for i in range(nn):
    value[i],weight[i]=map(int,input().split())    
    
dp=[[0]*(ww+1) for i in range(nn+1)]
for w in range(ww+1):
    dp[0][w]=0
    
for i in range(nn):
    for w in range(ww+1):
        if weight[i]<=w:
            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[nn][ww])

Solution (Python):





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

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












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

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

print(dp[N][W])

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

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

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

print(dp[N][W])

Solution (Python):
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue



ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, W = il()
    VW = [il() 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 >= VW[i][1]:
                dp[i+1][w] = max(VW[i][0] + dp[i][w-VW[i][1]], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    print(dp[N][W])


if __name__ == '__main__':
    main()

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

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

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

print(dp[N][W])

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

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

for i in range(n):
    cv, cw = IN[i]
    for j in range(w + 1):
        if j - cw >= 0:
            DP[i + 1][j] = max(DP[i][j - cw] + cv, DP[i][j])            
        else:
            DP[i + 1][j] = DP[i][j]
print(max(sum(DP, [])))

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

dp = [0] * (W+1)
for i in range(N):
    vi, wi = map(int, input().split())
    ndp = [0] * (W+1)
    for j in range(W+1):
        if j < wi:
            ndp[j] = dp[j]
        else:
            ndp[j] = max(dp[j-wi] + vi, dp[j])
    dp = ndp
print(dp[W])

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

N, W = MAP()

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

for i in range(N):
	v[i], w[i] = MAP()

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

print(dp[W])

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

for i in range(N):
    vi, wi = map(int, input().split())
    value.append(vi)
    weight.append(wi)



dp = [[0]*(10**4+10) for _ in range(110)]
def rec(i,w):
    dp[i+1][w] = dp[i][w] 

    if w-weight[i] >= 0:
        dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])

for i in range(N):
    for j in range(W+1):
        rec(i,j)
print(dp[N][W])

Solution (Python):
n, w = map(int, input().split())
weight = [0] * n
values = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    weight[i] = b
    values[i] = a

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

dp = [[0] * (w + 10) for _ in range(n + 10)]
for i in range(n):
    for sum_w in range(w + 1):
        if sum_w >= weight[i]:
            dp[i + 1][sum_w] = chmax(dp[i][sum_w - weight[i]] + values[i], dp[i][sum_w])
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

print(dp[n][w])

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

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

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

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

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

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

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

print(dp[n][w])

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

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

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

print(dp[N][W])

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

dp=[[0]*10010 for _ in range(110)]
for i in range(1,N+1):
    for j in range(0,W+1):
        if j < a[i][1]:
            dp[i][j]= dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i][1]]+a[i][0])
print(dp[N][W])

Solution (Python):
if __name__ == "__main__":
    n, w = map(int, input().split())
    v = []
    ws = []
    for _ in range(n):
        vi, wi = map(int, input().split())
        v.append(vi)
        ws.append(wi)
    
    dp = []
    for _ in range(n + 1):
        dp.append([0] * (w + 1))
    
    
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            dp[i][j] = dp[i - 1][j]
            if j - ws[i - 1] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - ws[i - 1]] + v[i - 1])
    ans = (-1) * float('inf')
    print(max(dp[n]))

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

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

print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
jw = [list(map(int, input().split())) for _ in range(N)]
ans = [[0 for _ in range(W + 1)] for __ in range(N)]
for w in range(W + 1):
    if w >= jw[0][1]:
        ans[0][w] = jw[0][0]
    else:
        pass
for n in range(1, N):
    for w in range(W + 1):
        if w < jw[n][1]:
            ans[n][w] = ans[n-1][w]
        else:
            ans[n][w] = max(ans[n-1][w], ans[n-1][w - jw[n][1]] + jw[n][0])
print(ans[N-1][W])

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

def main():
    N,W = map(int,input().split())
    item = [tuple(map(int,input().split())) for _ in range(N)]
    dp = [0] * (W + 1)
    for v,w in item:
        for j in range(W,w - 1,-1):
            dp[j] = max(dp[j],dp[j - w] + v)
    print(dp[-1])
if __name__ == '__main__':
    main()

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

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

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

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

print(C[N][W])

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,W,*vw = map(int, read().split())

    VW = []
    for v, w in zip(*[iter(vw)]*2):
        VW.append((v, w))

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

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

    print(dp[N][W])    


if __name__ == "__main__":
    main()

Solution (Python):


def solve():
    import sys

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

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

    for i in range(1, N+1):
        v, w = list(map(int, sys.stdin.readline().split()))
        for j in range(0, W+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j+w <= W:
                dp[i][j+w] = max(dp[i-1][j+w], dp[i-1][j]+v)

    print(dp[N][W])


if __name__ == "__main__":
    solve()