Problem:
 Score : 100 points    Problem Statement There are N items, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N ), Item i has a weight of w_i and a value of v_i .  Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W , which means that the sum of the weights of items taken must be at most W .  Find the maximum possible sum of the values of items that Taro takes home.      Constraints  All values in input are integers.  1 \leq N \leq 100  1 \leq W \leq 10^5  1 \leq w_i \leq W  1 \leq v_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  W  w_1  v_1  w_2  v_2  :  w_N  v_N       Output Print the maximum possible sum of the values of items that Taro takes home.        Sample Input 1 3 8
3 30
4 50
5 60      Sample Output 1 90  Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8 , and the sum of the values is 30 + 60 = 90 .       Sample Input 2 5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000      Sample Output 2 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 3 6 15
6 5
5 6
6 4
6 6
3 5
7 2      Sample Output 3 17  Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14 , and the sum of the values is 6 + 6 + 5 = 17 .

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

Solution (Python):
N, W = map(int, input().split())
wv = [list(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 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[N][W])

Solution (Python):
n,w = map(int,input().split())
w_i = [0]
v_i = [0]
for i in range(n):
  temp = list(map(int,input().split()))
  w_i.append(temp[0])
  v_i.append(temp[1])

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

for i in range(1,n+1):

  for j in range(w+1):
    temp_1 = -float("inf")
    if j-w_i[i] >= 0:
      temp_1 = dp[i-1][j-w_i[i]] + v_i[i]
    
    temp_2 = dp[i-1][j]
    
    if temp_1 <= temp_2:
      dp[i][j] = temp_2
    elif temp_2 < temp_1:
      dp[i][j] = temp_1
      
print(dp[n][w])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
for i in range(n):
	item.append(LI())

def main():
	dp = [0]*(w+1)
	for i in range(n):
		for j in range(w,item[i][0]-1,-1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[w])

if __name__ == '__main__':
	main()

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

Solution (Python):
from sys import stdin


def ii(): return int(stdin.readline())
def fi(): return float(stdin.readline())
def mi(): return map(int, stdin.readline().split())
def fmi(): return map(float, stdin.readline().split())
def li(): return list(mi())
def lsi():
    x=list(stdin.readline())
    x.pop()
    return x
def si(): return stdin.readline()

n, w=mi()
a=[[0] for _ in range(n+1)]
for _ in range(w):
    a[0].append(0)
for i in range(1, 1+n):
    x, v=mi()
    for j in range(1, 1+w):
        if j>=x:
            a[i].append(max(a[i-1][j-x]+v, a[i-1][j]))
        else:
            a[i].append(a[i-1][j])
print(a[-1][-1])

Solution (Python):
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
dp = [[0]*(W+1) for i in range(N+1)]
cnt = [[0]*(W+1) for i in range(N+1)]
a = []
b = []

for i in range(N):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    a.append(A)
    b.append(B)

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

print(dp[N][W])

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

Solution (Python):


import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7


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

Solution (Python):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, k = map(int, readline().split())
dp = np.zeros(k + 1)

for i in range(n):
    w, c = map(int, readline().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)

print(int(dp[-1]))

Solution (Python):
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            dion = dio[j-wi]+vi
            if dion > dio[j]:
                di[j] = dion
            else:
                di[j] = dio[j]
    print(dp[-1][-1])

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 = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

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

Solution (Python):
n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
dp = [[-1]*(wei+1) for x in range(n+1)]
for i in range(wei+1):
    dp[0][i] = 0

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

Solution (Python):
N, W, *A = map(int, open(0).read().split())
A = zip(*[iter(A)]*2)


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

for i, (w, v) in enumerate(A):
    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[N]))

Solution (Python):
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    x,v=map(int,input().split())
    weight.append(x)
    value.append(v)
    
dp=[[0 for i in range(w+1)]for i in range(n+1)]

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

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

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


Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
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

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

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

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

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

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

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

print(dp[N][W])

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

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

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

print(dp[N][W])

Solution (Python):
from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i, j in product(range(N), range(W+1)):
        u = dp[i][j]
        if j - pairs[i][0] >= 0:
            u = max(u, dp[i][j-pairs[i][0]]+pairs[i][1])
        dp[i+1][j] = u
    return max(dp[N])

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
n, m = map(int, input().split())
inf = 10**8
dp = [-inf] * (m + 1)
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    for j in range(m - w, -1, -1):
        if dp[j] != -inf:
            dp[j + w] = max(dp[j + w], dp[j] + v)
print(max(dp))

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

Solution (Python):
MAX_N = 110
MAX_W = 10 ** 5 + 100
N, W = map(int, input().split())
w = [0] * MAX_N
v = [0] * MAX_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 sum_w in range(W + 1):
        if sum_w - w[i] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i])
        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())
p = [list(map(int, input().split())) for _ in range(n)]
p.insert(0, [0, 0])
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 >= p[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i][0]] + p[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])

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


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

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

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

Solution (Python):
MAX_N = 110
N, W = map(int, input().split())
weight = [0] * MAX_N
value = [0] * MAX_N
for i in range(N):
    weight[i], value[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(MAX_N)]
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 = [int(i) for i in 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):
    w_i, v_i = wv[i]
    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[-1][-1])

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

Solution (Python):
n, lim_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]*(lim_w+1) for _ in range(n+1) ]

for i in range(n):
    for j in range(lim_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][lim_w])

Solution (Python):
def main():
    goods, weight_limit = map(int, input().split())
    weight = []
    value = []
    for _ in range(goods):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    dp = [[0 for _ in range(weight_limit + 1)] for _ in range(goods + 1)]
    for i in range(goods):
        for j in range(weight_limit + 1):
            if j >= weight[i]:
                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[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math


def dpp(a, b=""): print(")

def read():
    n, w = rrl()
    l = [rrt() for _ in range(n)]

    return n, w, l

def solve(n, w, l):
    dp = ms(w+1, n+1)

    for wi in range(1, w+1):
        for ii in range(1, n+1):
            if l[ii-1][0] > wi:
                dp[wi][ii] = dp[wi][ii-1]
            else:
                dp[wi][ii] = max(
                        dp[wi][ii-1],
                        dp[wi-l[ii-1][0]][ii-1] + l[ii-1][1],
                        )
    

    ans = dp[w][n]
    return ans

if __name__ == "__main__":
    
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

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

we = []
v = []
for i in range(n):
	ww,vv = map(int,input().split())
	we.append(ww)
	v.append(vv)
for i in range(n):
	for j in range(w+1):
		if we[i] <= j:
			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())

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

print(dp[N][W])

Solution (Python):
def knapsack(N, W, weight, value):
  inf = float("inf")
  dp = [[-inf]*(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 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]
  return dp[N][W]
  
N, W = map(int, input().split())
weight, value = [], []
for i in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)

print(knapsack(N, W, weight, value))

Solution (Python):















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

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

Solution (Python):
import sys


def main():
    input = sys.stdin.readline

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

    WV = (map(int, input().split()) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            tmp = dp[j - w] + v
            if tmp > dp[j]:
                dp[j] = tmp

    print(dp[-1])


main()

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

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

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

print(dp[mw])

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

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


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

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 _ 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] = 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] * (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().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

dp = [[0] * (W+1) for i in range(N)]
for i in range(W+1):
    dp[0][i] = oj[0][1] if oj[0][0] <= i else 0

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

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

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

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

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

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

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

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

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

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

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

print(dp[N][W])

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

    return max(dp[N])

print(DP_D())

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

Solution (Python):
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
dp = [[0 for w in range(W+1)] for n in range(N+1)]
for i in range(W+1):
	dp[0][i] = 0
for p in range(1, N+1):
	for q in range(W+1):
		dp[p][q] = dp[p-1][q]
		if (A[p-1][0] <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - A[p-1][0]] + A[p-1][1])

print(dp[N][W])

Solution (Python):
n,cap=map(int,input().split())
weigh=[]
profit=[]
temp=n
while temp!=0:
    w,p=map(int,input().split())
    weigh.append(w)
    profit.append(p)
    temp-=1

mat=[[0 for i in range(cap+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,cap+1):
        if j<weigh[i-1]:
            mat[i][j]=mat[i-1][j]
        else:
            mat[i][j]=max(profit[i-1]+mat[i-1][j-weigh[i-1]],mat[i-1][j])
print(mat[n][cap])

Solution (Python):
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

WV = [[int(x) for x in input().split()] for _ in range(N)]

dp = [np.zeros(W*2 + 10, dtype=np.int64) for _ in range(N+1)]

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


ans = dp[N][W]

print(ans)

Solution (Python):
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


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


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))




if __name__ == "__main__":
    n, w = rinput()
    w_v = []
    for i in range(n):
        w_v.append(rlinput())
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    
    for item in range(1, n+1):
        for weight in range(1, w+1):
            if weight >= w_v[item-1][0]:
                dp[item][weight] = max(dp[item-1][weight-w_v[item-1][0]]+w_v[item-1][1],dp[item-1][weight])
            else:
                dp[item][weight] =dp[item-1][weight]
    print(dp[n][w])

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

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

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

for i in range(n):
    for mw in range(w + 1):
        if weight[i] <= mw:
            dp[i + 1][mw] = max(dp[i][mw], dp[i][mw - weight[i]] + value[i])
        else:
            dp[i + 1][mw] = dp[i][mw]

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

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

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

Solution (Python):
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
 
dp = [0] * (w+1)
for wi, vi in wv:
    for sum_w in reversed(range(wi, w+1)):
        dp[sum_w] = max(dp[sum_w], dp[sum_w - wi] + vi)
print(dp[w])

Solution (Python):
n, w = map(int, input().split())
elems = []
for _ in range(n):
    elems.append(list(map(int, input().split())))
res = [0] * (w + 1)
for item in elems:
    for j in range(w, item[0] - 1, -1):
        res[j] = max(res[j], res[j - item[0]] + item[1])

print(res[-1])

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

Solution (Python):
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()