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

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

    for i in range(N-1,-1,-1):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w_v[i][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[0][W])
 
if __name__ == "__main__":
    resolve()

Solution (Python):

import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s


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

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

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    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-1]-1:
                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])
    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 itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): 
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(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[0][W])
if __name__ == "__main__":
    main()

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

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

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

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

ret = 0
for i in dp:
    ret = max(ret, i[-1])
print(ret)

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

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

ret = 0
for i in dp:
    ret = max(ret, i[-1])
print(ret)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): 
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(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[0][W])
if __name__ == "__main__":
    main()

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

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

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

print(dp[-1])

Solution (Python):
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

DP = [[0 for _ in range(W + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for w in range(W + 1):
        if w - weight >= 0:
            DP[i+1][w] = max(DP[i][w - weight] + value, DP[i][w])
        else:
            DP[i+1][w] = DP[i][w]

print(DP[M][W])

Solution (Python):
def main(n,w,item):
    
    
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            
            weight, value = item[i]
            if j+weight <= w:
                dp[i+1][j+weight] = max(dp[i+1][j+weight], dp[i][j]+value)
            
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    return max(dp[-1])

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

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

def main():
    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(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):
        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(max(dp[n]))

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

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

    print (dp[W])

if __name__ == '__main__':
    main()

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

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)

print (dp[W])

Solution (Python):

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

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

for i in range(n):
    w, v = map(int,input().split())
    for sumw in range(mw + 1):
        if sumw - w >= 0:
            dp[i + 1][sumw] = max(dp[i][sumw], dp[i][sumw - w] + v)
        else:
            dp[i + 1][sumw] = dp[i][sumw]

print(dp[n][mw])

Solution (Python):
N,W = map(int,input().split())
w_list = []
v_list = []
for _ 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):
    w = w_list[i-1]
    v = v_list[i-1]
    for j in range(1,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):
import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])

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

for w, v in wv:
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)
    
print(dp[-1])

Solution (Python):
import numpy as np

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

for w, v in wv:
    dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)
    
print(dp[-1])

Solution (Python):
import numpy as np

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

for w, v in wv:
    dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)
    
print(dp[-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] = 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())

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

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

print(dp[-1])

Solution (Python):
import numpy as np
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

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

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

print(dp[n][W])

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

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

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

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

Solution (Python):
from collections import namedtuple


Item = namedtuple('Item', 'w v')

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

items = []

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

memo = [0] * (W + 1)

for item in items:
  for w in range(W, item.w - 1, -1):
    memo[w] = max(memo[w], memo[w - item.w] + item.v)
    
print(memo[W])

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

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

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 nimotsu in range(N):
    
    w_weight, w_val = map(int, input().split())
    
    for w in range(W+1):
        
        sum_ = w + w_weight
        if sum_ <= W :
            dp[nimotsu+1][sum_] = max(dp[nimotsu+1][sum_], dp[nimotsu][w] + w_val)
            
        
        dp[nimotsu+1][w] = max(dp[nimotsu+1][w] ,dp[nimotsu][w])

print(dp[N][W])

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

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

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

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    
print(DP[-1])

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

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

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

print(max(dp[-1]))

Solution (Python):
N, WW = map(int, input().split())
W, V = [], []
for _ in range(N):
    _w, _v = list(map(int, input().split()))
    if _w > WW:
        continue
    W.append(_w)
    V.append(_v)

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

print(dp[N][WW])

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

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

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] * (W + 1) for i 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]

print(dp[N][W])

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

dp = [[0 for i in range(W)] for j in range(N)]

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

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

Solution (Python):



import numpy

def main():
  n, w = map(int, input().strip().split())
  Ws, Vs = numpy.array([[int(x) for x in input().strip().split()] for _ in range(n)]).T
  dp = numpy.zeros((n, w+1), dtype=numpy.int)
  dp[0, Ws[0]:] = Vs[0]
  for i in range(1, n):
    dp[i] = dp[i-1,:]
    if w - Ws[i] + 1 > 0:
      dp[i, Ws[i]:w+1] = numpy.maximum(dp[i-1, Ws[i]:w+1], dp[i-1,:w-Ws[i]+1]+Vs[i])
  print(dp[n-1, w])


if __name__=='__main__':
  main()

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

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

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

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

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

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

N, W = map(int, input().split())
B = [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 = B[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):
n, w = map(int, input().split())
dp = [0]*(w+1)

for i in range(n):
  weight, value = map(int, input().split())
  for j in range(w, -1, -1):
    if j == 0 or dp[j] != 0:
      if j+weight <= w:
        dp[j+weight] = max([dp[j+weight], dp[j]+value])

print(max(dp))

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

Solution (Python):
N,W = [int(i) for i in input().split()]
dp = [0 for i in range(W+1)] 
for i in range(N):
  w,value = [int(i) for i in input().split()]
  for weight in range(W-w, -1, -1): 
    dp[weight + w] = max(dp[weight + w], dp[weight] + value)
print("%s" % dp[W])

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])

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

for i in range(N):
    for j in range(W + 1):
        w, v = wv[i]
        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):
def main():
    import sys
    readline = sys.stdin.readline

    n, w = map(int, readline().split())

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

    for i in range(1, n + 1):  
        wi, vi = map(int, readline().split())
        for j in range(wi):
            dp[i][j] = dp[i - 1][j]
        for j in range(wi, w + 1):
            dp[i][j] = max(
                dp[i - 1][j],  
                dp[i - 1][j - wi] + vi
            )

    print(max(dp[n]))


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

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

Solution (Python):

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



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



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



for i in range(n):
    
    for sum_w in range(w+1):
        
        
        if sum_w>=W[i]:
            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(int(dp[n][w]))

Solution (Python):
def main():
    import numpy as np
    import sys
    input = sys.stdin.readline

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

    dp = np.zeros((n+1,w+1),dtype="int64")
    for i in range(n):
        dp[i+1][:l[i][0]] = dp[i][:l[i][0]]
        dp[i+1][l[i][0]:] = np.maximum(dp[i][l[i][0]:],dp[i][:-l[i][0]]+l[i][1])
    print(dp[n][w])

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n,w = map(int,input().split())
    l = [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(w+1):
            if j-l[i-1][0] >= 0:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n][w])
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np 
IN = lambda:map(int, input().split())
 
n, k = IN()
dp = np.zeros(k + 1)
 
for i in range(n):
    w, c = IN()
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)
    
print(int(dp[-1]))

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

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

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

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

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

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

MAX_W = 10 ** 5


DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  
            DP[i][j] == 0
        elif j < WE[i]:  
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])



print(DP[0][W])

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 for i in range(W+1)] for i in range(N)]
for i in range(N):
    w = w_list[i]
    v = v_list[i]
    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-1][W])

Solution (Python):
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 = [[0]*(W+1) for _ in range(n+1)]

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

print(dp[n][W])

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

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

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

print(dp[-1][W])

Solution (Python):
def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    vdp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for weight in range(W+1):
            
            if weight >= w[i]: vdp[i+1][weight] = max(vdp[i][weight - w[i]] + v[i], vdp[i][weight])
            
            vdp[i+1][weight] = max(vdp[i+1][weight], vdp[i][weight])
    print(vdp[N][W])

if __name__ == '__main__':
    main()