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, max_weight = map(int, input().split())
dp = [[0 for _ in range(max_weight+1)] for _ in range(n+1)]

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

Solution (Python):
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv =L[i][0], L[i][1] 
    dp[i+1][Lw] = Lv 
    for w, v in dp[i].items():
        dp[i+1][w] = max(dp[i+1].get(w, 0), v) 
        if w + Lw <=limit:
            dp[i+1][w+Lw] = max(dp[i].get(w+ Lw, 0), Lv + v) 
        
print(max(dp[-1].values()))

Solution (Python):
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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

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

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

print(dp[N][W])

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

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

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


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

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

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

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

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

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

print(dp[N][W])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*n; V=[0]*n
    for i in range(n):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for k in range(w+1):
            if k-W[i-1]>=0:
                dp[i][k]=max(dp[i-1][k-W[i-1]]+V[i-1],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

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

Solution (Python):
"""
ナップサック問題
"""
N,W = map(int, input().split())
dp = [[-1 for i in range(100100)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if dp[i][j] == -1:
            continue
        elif j+w <= W:
            
            dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
            

print(max(dp[N][:W+1]))

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

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

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())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)

Solution (Python):

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,W = LI()
wv = [LI() for _ in range(n)]
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v = wv[i]
    for j in range(w):
        dp[i+1][j] = dp[i][j]
    for j in range(W+1):
        if w + j > W:
            break
        dp[i+1][w+j] = max(dp[i][w+j],dp[i][j] + v)
    
print(max(dp[-1]))

Solution (Python):
from heapq import heappop, heappush
from operator import itemgetter


def branchAndBound(N: int, M: int, V: list, W: list, R: list) -> int:
    def upperbound(w, v, i):
        rest = M - w
        _v = v
        for j in range(i + 1, N):
            if W[j] >= rest:
                rest -= W[j]
                v += V[j]
                _v = v
            else:
                _v += R[j] * rest
                break
        return v, _v

    prov, tmp = upperbound(0, 0, -1)
    h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]
    while h:
        _v, w, v, cur = heappop(h)
        if _v > prov or cur == N - 1:
            continue
        nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
        if nxtw >= M:
            heappush(h, (_v, nxtw, nxtv, cur + 1))
        _prov, ub = upperbound(w, v, cur)
        if _prov < prov:
            prov = _prov
        if ub < prov:
            heappush(h, (ub, w, v, cur + 1))
    return -prov


def main():
    N, M, *L = map(int, open(0).read().split())
    t = [(v, w, v / w) for w, v in zip(*[iter(L)] * 2)]
    t.sort(key=itemgetter(2), reverse=True)
    V, W, R = [], [], []
    for v, w, r in t:
        V += [-v]
        W += [-w]
        R += [r]
    ans = branchAndBound(N, -M, V, W, R)
    print(ans)
    
if __name__=="__main__":main()

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

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

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
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-l[i-1][0]>=0:
      dp[i][j]=max(dp[i-1][j-l[i-1][0]]+l[i-1][1],dp[i-1][j])
    else:
      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())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7



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

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

dp=[0]*(w+1)

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

Solution (Python):
import sys
n, limit= map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


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


for w in range(limit+1):
    if L[0][0] <=w:
        dp[0][w] = L[0][1]

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

print(max(dp[-1]))

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7



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 _ in range(N+1) ]

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

print(dp[N][W])

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

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

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

print(max(dp[-1]))

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

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

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, -1, -1):
            if j + w[i] <= W:
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])
    ret = max(dp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

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

Solution (Python):
from copy import deepcopy
N, K = [int(i) for i in input().split()]
wvs = [(int(w), int(v)) for w,v in [input().split() for _ in range(N)]]
dp = [0]*(K)
for i, wv in enumerate(wvs):
  w,v = wv
  tmp_dp = deepcopy(dp)
  for j in range(i,K):
    if (j+w) <= K:
      tmp_dp[j+w-1] = max(dp[j+w-1], dp[j-1] + v)
  dp = tmp_dp
print(max(dp))

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

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

Solution (Python):
n, w = map(int, input().split())
ws = [0] * n
vs = [0] * n
for i in range(n):
    ww, vv = map(int, input().split())
    ws[i] = ww
    vs[i] = vv

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

print(dp[n][w])

Solution (Python):

def main():
    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 - w, -1, -1):
            dpi = dp[i]
            if dpi != -1:
                if dp[i + w] < dpi + v:
                    dp[i + w] = dpi + v
    print(max(dp))


main()

Solution (Python):

def main():
    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 - w, -1, -1):
            dpi = dp[i]
            if dpi == -1:
                continue
            if dp[i + w] < dpi + v:
                dp[i + w] = dpi + v
    print(max(dp))


main()

Solution (Python):

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

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


main()

Solution (Python):
import sys
n, W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0 for _ in range(W+1)] for _ in range(n)]
for w in range(W+1):
    if w>=L[0][0]:
        dp[0][w] = L[0][1]


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

print(max(dp[-1]))

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

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

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

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

print(dp[n][w])

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

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


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

print(DP[N][W])

Solution (Python):
n, w = map(int,input().split())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

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

print(dp[n][w])

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

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

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

print(dp[N][W])

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

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

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

def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            a = dp[sum_w - w] + v
            if a > dp[sum_w]:
                dp[sum_w] = a
    print(dp[-1])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            tv = dp[sum_w - w] + v
            if tv > dp[sum_w]:
                dp[sum_w] = tv
    print(dp[-1])

if __name__ == '__main__':
    main()

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

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

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

print(dp[N][W])

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

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

Solution (Python):
def main():
    n, w = map(int, input().split())
    dp = [-1] * (w + 1)
    dp[w] = 0
    for i in range(n):
        input_w, input_v = map(int, input().split())
        for i in range(input_w, w + 1):
            if dp[i] == -1:
                continue
            if dp[i - input_w] < dp[i] + input_v:
                dp[i - input_w] = dp[i] + input_v
    print(max(dp))

main()