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):
weights, values = [], []

n, w = list(map(int, input().split()))
for _ in range(n):
    w_c, v_c = list(map(int, input().split()))
    weights.append(w_c)
    values.append(v_c)

dp = [[0 for i in range(w + 1)] for i in range(n + 1)]
for i in range(len(values) + 1):
    for j in range(w + 1):
        if i == 0 or j == 0: 
            dp[i][j] = 0
        elif weights[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]
    
print(dp[-1][-1])

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

Solution (Python):

def main():
    
    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) for i 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 - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

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


if __name__ == '__main__':
    main()

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

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

Solution (Python):
N,W = [int(c) for c in input().split()]
wv = [[int(c) for c in input().split()] for d in range(N)]

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

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

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

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


def wi(i):
    return wv[i - 1][0]


def vi(i):
    return wv[i - 1][1]


def value(i, w):
    if w - wi(i) >= 0:
        return max(dp[i - 1][w], dp[i - 1][w - wi(i)] + vi(i))
    else:
        return dp[i - 1][w]


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

print(dp[-1][-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 + 2) for i in range(N + 2)]
"""
DP[0][W]
DP[i][j]
i:荷物の個数
j:残り容量
"""
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(max(DP[N]))

Solution (Python):
def main():
    N, Wei = 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] * (Wei + 5) for _ in range(N + 5)]
    dp[0][Wei] = 0
    for i in range(N):
        for w in range(Wei+1):
            if w >= W[i]:
                dp[i+1][w] = max(dp[i][w-W[i]] + V[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]

    print(dp[N][Wei])


if __name__ == "__main__":
    main()

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

    dp = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[w])


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

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())
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (W + 1)

for w, v in wv:
    for i in range(W, 0, -1):
        if i - w < 0:
            break

        dp[i] = max(dp[i], dp[i - w] + v)
            
print(dp[W])

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


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

Solution (Python):
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
N, M = map(int, input().split())
dp = [[0]*(M+1) for _ in range(N+1)]

for i in range(1, N+1):
    W,V = map(int, input().split())
    for j in range(0,M+1):
        dp[i][j] = max(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)

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[i][j])
    print('')
'''

print(max(dp[-1]))

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

for i in range(1, N+1):
    W,V = map(int,input().split())
    for j in range(W):
        dp[i][j] = dp[i-1][j]
    for j in range(M-W+1):
        dp[i][j+W] = max(dp[i-1][j+W],dp[i-1][j]+V)

print(max(dp[-1]))

Solution (Python):
def getval():
    n,w = map(int,input().split())
    p = [list(map(int,input().split())) for i in range(n)]
    return n,w,p 

def main(n,w,p):
    
    dp = [[0 for i in range(w+1)]]
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(w+1):
            cur = dp[i][j]
            if j>=item[0]:
                cur = max(cur,dp[i][j-item[0]]+item[1])
            temp.append(cur)
        dp.append(temp)
    print(dp[n][w])
                
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

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

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

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


if __name__ == "__main__":
    main()

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

for i in range(n):
    temp_w,temp_v=map(int,input().split())
    w.append(temp_w)
    v.append(temp_v)
    

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

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

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

    dp = [0] * (w + 1)
    for weight, value in wv:
        for i in range(w - weight + 1)[::-1]:
            if dp[i + weight] < dp[i] + value:
                dp[i + weight] = dp[i] + value

    print(dp[w])

main()

Solution (Python):
from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

mod=1000000007
INF=float('inf')

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1]  + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
    

x=[]
y=[]
n,w=mp()
for i in range(n):
    a,b=mp()
    x.append(a)
    y.append(b)

print(knapSack(w,x,y,n))

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

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

print(dp[N][W])

Solution (Python):

import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

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

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

if __name__ == '__main__':
    main()

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

INF = 10**18
dp = [[-INF]*(W+1) for _ in range(n+1)]
dp[0][0] = 0

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

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n, w = li()
l = []
for i in range(n):l.append(li())

l.sort()

knapsack = [0] * (w + 1)
for i in l:
    for j in range(w - i[0], -1, -1):
        if not j or knapsack[j]:
            knapsack[j + i[0]] = max(knapsack[j + i[0]], knapsack[j] + i[1])

print(max(knapsack))

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 i in range(n+1)]

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

Solution (Python):
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''


import sys
import os
from io import BytesIO, IOBase
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")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")



mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
        ans = 1
        for i in range(1, x+1): ans = (ans * i) % mod
        return ans
def arr2D(n, m, default=0):
        lst = []
        for i in range(n): temp = [default] * m; lst.append(temp)
        return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, W, weight, value):
    dp = arr2D(n+1, W+1)

    for i in range(1, n+1):
        for j in range(1, W+1):
            
            val = max(dp[i][j-1], dp[i-1][j])
            if j >= weight[i-1]:
                dp[i][j] = max(val, dp[i-1][j-weight[i-1]] + value[i-1])
            else: dp[i][j] = val
    return dp[n][W]

n, W = list(map(int, input().split()))
weight = []
value = []
for i in range(n):
        a, b = list(map(int, input().split()))
        weight.append(a)
        value.append(b)
print(solve(n, W, weight, value))

Solution (Python):
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]







dp = [[0] * (W+1) for _ in range(N)]
sw, sv = L[0][0], L[0][1]
dp[0][0] = 0
dp[0][sw] = sv
for i in range(1, N):
    cw, cv = L[i][0], L[i][1]
    for w in range(W):
        
        dp[i][w] = max(dp[i][w], dp[i-1][w])
        
        if w + cw > W:
            continue
        dp[i][w + cw] = max(dp[i][w + cw], dp[i-1][w] + cv)

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

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

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

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

print(dp[N][W])

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

Solution (Python):
import numpy as np
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((n+1, W+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, :W-w[i]+1]+v[i])

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

Solution (Python):
n, w = map(int, input().split())
W = [0 for i in range(n)]
V = [0 for i in range(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)]
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] >= 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[n - 1][w])

Solution (Python):
n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    a,b=map(int,input().split())
    W.append(a)
    V.append(b)
dp=[[0]*(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):
import numpy as np
[N,W],*h = [list(map(int,i.split())) for i in open(0)]

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

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

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

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

for i in range(n):
    w = li[i][0]
    v = li[i][1]
    for k in range(W+1):
        if  w>k:
            dp[i+1][k] = dp[i][k]
            continue
        dp[i+1][k] = max(dp[i][k-w]+v,dp[i][k])
print(dp[n][W])

Solution (Python):
def getval():
    n,w = map(int,input().split())
    p = [list(map(int,input().split())) for i in range(n)]
    return n,w,p 

def main(n,w,p):
    
    dp = [[0 for i in range(w+1)]]
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(w+1):
            cur = dp[i][j]
            if j>=item[0]:
                cur = max(cur,dp[i][j-item[0]]+item[1])
            temp.append(cur)
        dp.append(temp)
    print(dp[n][w])
                
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

Solution (Python):
def solve(items, W):
    dp = [[0]*(W+1) for _ in range(len(items)+1)]

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

    return dp[len(items)][W]


if __name__ == "__main__":
    N, W = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(N)]
    print(solve(items, W))

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

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 wgt in range(1,ww+1):
            if wgt - w < 0:
                dp[i][wgt] = dp[i-1][wgt]
                continue
            dp[i][wgt] = max(dp[i-1][wgt], dp[i-1][wgt-w]+v)
            
    print(max(dp[i]))
    
if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



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

def main():
    n, w = map(int, input().split())
    weight_list = []
    value_list = []
    wv_list = []
    for i in range(n):
        weight, value = map(int, input().split())
        weight_list.append(weight)
        value_list.append(value)
    
    dp = [[0] * (w+1) for i in range(n)]
    for i in range(w+1):
        if weight_list[0] <= i:
            dp[0][i] = value_list[0]
    for i in range(1, n):
        for j in range(0, w+1):
            if weight_list[i] <= j:
                
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_list[i]] + value_list[i])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[-1][-1])
if __name__ == "__main__":
    main()

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

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

import numpy as np

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

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

Solution (Python):
'''
Created on 2020/09/15

@author: harurun
'''
import sys
pin=sys.stdin.readline


N,W=map(int,pin().split())
dp=[[0]*(W+1) for _ in [0]*(N+1)]

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

Solution (Python):
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [-1] * (W + 1)
DP[0] = 0

for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if d < 0:
            continue
        if i + w > W:
            break
        D[i + w] = max(D[i + w], d + v)
    DP = D
print(max(DP))

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys



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


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

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



    print(max(dp))





if __name__ == "__main__":
    main()

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

DP = [[0] * (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][j-1], DP[i-1][j])
        if j - w >= 0:
            DP[i][j] = max(DP[i][j], DP[i-1][j-w] + v)

print(DP[N][W])

Solution (Python):
import sys
N, W = map(int, input().split())
X =[[0,0]] + [list(map(int, input().split())) for _ in range(N)]

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

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

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

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

print(dp[N][W])

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

Solution (Python):
n,w=map(int, input().split())
g=[0]
v=[0]
for i in range(n):
    G,V=map(int, input().split())
    g.append(G)
    v.append(V)

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

print(dp[n][w])

Solution (Python):

def main():
    import sys
    import numpy as np

    read = sys.stdin.read

    N, W = map(int, input().split())
    wv = np.array(read().split(), dtype=np.int64)
    w = wv[::2]
    v = wv[1::2]

    dp = np.zeros(W + 1, dtype=np.int64)
    for can_w, can_v in zip(w, v):
        dp[can_w:] = np.maximum(dp[can_w:], dp[:-can_w] + can_v)

    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import sys
    import numpy as np

    read = sys.stdin.read

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

    dp = np.zeros(W + 1, dtype=np.int64)
    for can_w, can_v in zip(products, products):
        dp[can_w:] = np.maximum(dp[can_w:], dp[:-can_w] + can_v)

    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import numpy as np

    N, W = map(int, input().split())
    products = [list(map(int, input().split())) for _ in range(N)]

    dp = np.zeros(W + 1, dtype=np.int64)
    for can_w, can_v in products:
        dp[can_w:] = np.maximum(dp[can_w:], dp[:-can_w] + can_v)

    print(np.max(dp))


if __name__ == '__main__':
    main()

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def knapsack(limit, values, weights):
    """Returns the maximum value that can be reached using given weights"""
    n = len(weights)
    dp = [0]*(limit+1)
    for i in range(n):
        for j in range(limit, weights[i]-1, -1):
            dp[j] = max(dp[j], values[i] + dp[j - weights[i]])
    return dp[-1]

for _ in range(int(input()) if not True else 1):
    
    n, w = map(int, input().split())
    
    weights = []
    values = []
    for i in range(n):
        x, y = map(int, input().split())
        weights += [x]
        values += [y]

    print(knapsack(w, values, weights))

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