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())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))

Solution (Python):
def input_li():
    return list(map(int, input().split()))

def input_int():
    return int(input())

N, W = input_li()

dp = [[0] * (W + 1) for _ in range(N + 1)]
wv_li = [input_li() for _ in range(N)]
now_w = 0
for i in range(N):
    for sum_w in range(W + 1):
        w, v = wv_li[i]
        if w > sum_w:
            
            dp[i + 1][sum_w] = dp[i][sum_w]
        else:
            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w] + v)
print(dp[N][W])

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

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

print(dp[n][w])

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

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

dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    weight, value = items[i][0], items[i][1]
    for w_limit in range(1,W+1):
        if w_limit - weight >= 0:
            dp[i][w_limit] = max(dp[i-1][w_limit], dp[i-1][w_limit-weight] + value)
        else:
            dp[i][w_limit] = dp[i-1][w_limit]
print(dp[n][W])

Solution (Python):
n, w = map(int, input().split())
dp = [0] * (w + 1)
for j in range(n):
	w1, v1 = map(int, input().split())
	i = w
	while i >= 0 and i - w1 >= 0:
		dp[i] = max(dp[i - w1] + v1, dp[i])
		i -= 1
print(max(dp))

Solution (Python):
N, W = map(int, input().split())
dp = [0] * (W + 1)
def dp_opt(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            tmp = dp[j-w] + v
            if tmp > dp[j]:
                dp[j] = tmp
    print(dp[-1])
dp_opt(N,W)

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate

input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]

MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
    
def fun(A,P,W,N):
    if N == 0 or W == 0:
        return 0
    dp = list2d(N+1,W+1,0)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if A[i-1] <= j:
                dp[i][j] = max(dp[i-1][j] , P[i-1] + dp[i-1][j - A[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[N][W]
N,W = ilele()
P = []
A = []
for i in range(N):
    a,b =ilele()
    A.append(a)
    P.append(b)
print(fun(A,P,W,N))

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

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:
            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][-1])

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


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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    L = [list(map(int, input().split())) for i in range(N)]
    
    V = [[0]*(W+1) for i in range(N+1)]

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

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq

N, W = list(map(int, input().split()))
INF = 10**10

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(1,W+1):
        if j-w < 0:
            p = -INF
        else:
            p = dp[i-1][j - w]

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

print(dp[N][W])

Solution (Python):
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)
def dp_opt(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            tmp = dp[j-w] + v
            if tmp > dp[j]:
                dp[j] = tmp
    print(dp[-1])
dp_opt(N,W)

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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])
 
if __name__ == '__main__':
	main()

Solution (Python):
import sys

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

def main():
    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(1,W+1):
        for i in range(1,N+1):
            if w - wv[i-1][0] >= 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[-1][-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])

if __name__ == '__main__':
	main()

Solution (Python):
import sys
import numpy as np

def main():
    n, w = map(int, sys.stdin.buffer.readline().split())
    dp = np.zeros(w+1, dtype = int)

    for x in sys.stdin.buffer.readlines():
        w, v = map(int, x.split())
        np.maximum(dp[w:] , dp[:-w] + v, out = dp[w:])
    print(dp.max())

if __name__ == '__main__':
    main()

Solution (Python):
import sys

def main():
    n, w = map(int, input().split())
    a = [list(map(int, x.split())) for x in sys.stdin.readlines()]
    dp = [[0]*(w+1) for _ in range(n+1)]

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

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

if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,W = IL()
data = ILL(N)

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

for i in range(N):
  w0,v0 = data[i]
  for w in range(W+1):
    dp[i+1][w] = max(dp[i+1][w],dp[i][w])
    if w+w0 <= W:
      dp[i+1][w+w0] = max(dp[i][w+w0],dp[i][w]+v0)

print(max(dp[-1]))

Solution (Python):




from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, w = iia()
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
arr = []
for i in range(n):
    arr.append(iia())
for i in range(1, n + 1):
    for j in range(w + 1):
        if j < arr[i - 1][0]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], arr[i - 1][1] + dp[i - 1][j - arr[i - 1][0]])
print(dp[-1][-1])

Solution (Python):
N, W = map(int, input().split())
dp = [[0]*100100 for _ in range(110)]

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

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

print(dp[N][W])

Solution (Python):
from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	
    for i in range(n):
      
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]


Knapsack1(n,w,wl,vl)

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

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

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

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

weights = [0]*n
values = [0]*n

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

print(dp[-1][-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(w+1)

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

Solution (Python):
N,W = map(int, input().split())
L = [0]*(W+1)
for i in range (N):
  X,Y = map(int, input().split())
  for j in range (W,X-1,-1):
    L[j] = max(L[j], L[j-X] + Y)
print(max(L))

Solution (Python):
"""
    Satwik_Tiwari ;) .
    24th july , 2020  - Friday
"""



from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  
from itertools import combinations as comb 
from itertools import permutations as permutate
from bisect import bisect_left as bl


from bisect import bisect_right as br
from bisect import bisect





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


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)






mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True




def solve():
    n,W = sep()
    w = [0]
    v = [0]
    for i in range(n):
        a,b = sep()
        w.append(a)
        v.append(b)

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


testcase(1)

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

Solution (Python):

import sys
input = sys.stdin.readline


def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    

def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp


def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);


def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 


def upper_bound(a, x, lo=0, hi = None):
    if hi == None:
        hi = len(a);
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo


def primefs(n):
    
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    
    
    return primes


def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 


def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b









def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;




def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x


def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime


MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    




def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    
    


def int_array():
    return list(map(int, input().strip().split()))

def str_array():
    return input().strip().split();


MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');



n, w = int_array();
val = []; wts = [];
dp = [[0 for _ in range(w + 1)] for __ in range(n + 1)];

for _ in range(n):
    x, y = int_array();
    wts.append(x); val.append(y);

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

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b

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


if __name__ == "__main__":
    main()

Solution (Python):





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



x = [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):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])

Solution (Python):
x,size=map(int,input().split())
weight=[]
value=[]
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[0 for i in range(size+1)] for j in range(len(weight))]
for i in range(len(weight)):
    dp[i][0]=0
for i in range(len(weight)):
    for j in range(1,size+1):
        if weight[i]>j:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
print(dp[len(value)-1][size])

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

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

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

print(dp[N][W])

Solution (Python):
from sys import stdin
n,w = map(int,stdin.readline().split())
dp = [0]*w
cou = []
for _ in range(n):
    cou.append(tuple(map(int,stdin.readline().split())))
for val in cou:
    for i in range(w-1,-1,-1):
        if dp[i] != 0 and i+val[0] < w:
            dp[i+val[0]] = max(dp[i+val[0]],dp[i]+val[1])
    dp[val[0]-1] = max(dp[val[0]-1],val[1])
print(max(dp))

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

Solution (Python):
(N, W), *D = [list(map(int, o.split())) for o in open(0)]
w, v = 0, 1
dp = [[0]*-~W for _ in [0]*-~N]
for i in range(N):
  for j in range(W + 1):
    dp[i + 1][j] = max(dp[i][j], (dp[i][j - D[i][w]] + D[i][v])*(j >= D[i][w]))
print(dp[N][W])

Solution (Python):
import sys


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


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

    print(dp[W][N])


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, w = ns()
    a = [na() for _ in range(n)]

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

    for wi, vi in a:
        for i in range(w - 1, -1, -1):
            if i + wi <= w and dp[i] > -1:
                dp[i + wi] = max(dp[i + wi], dp[i] + vi)

    print(max(dp))


if __name__ == '__main__':
    main()

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

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

Solution (Python):
def main():
    n, w = [int(x) for x in input().split()]
    itens = []
    dp = [[-1]*w for i in range(n)]
    
    for _ in range(n):
        itens.append([int(x) for x in input().split()])

    print(knapsack(n, w, itens, dp))

def knapsack(n, w, itens, dp):

    if n == 0 or w == 0:
        return 0

    if dp[n-1][w-1] != -1:
        return dp[n-1][w-1]

    if itens[n-1][0] > w:
        dp[n-1][w-1] = knapsack(n-1, w, itens, dp)
        return dp[n-1][w-1]

    else:
        dp[n-1][w-1] = max(itens[n-1][1] + knapsack(n-1, w - itens[n-1][0], itens, dp),
                           knapsack(n-1, w, itens, dp))

        return dp[n-1][w-1]

main()

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

dp=[]
for y in range(n+1):
    l=[]
    if y==0:dp.append([0]*(w+1));continue
    for x in range(w+1):
        if x==0:l.append(0);continue
        
        now_weight=x
        up_value=dp[-1][now_weight]

        index_weight=a[y-1][0]
        index_value=a[y-1][1]

        blank_weight=max(0,now_weight-index_weight)
        blank_max_value=dp[-1][blank_weight]
        

        t_value=up_value
        if now_weight>=index_weight:t_value=max(blank_max_value+index_value,up_value) 
        
        l.append(t_value)
        
    dp.append(l)

print(dp[n][w])

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

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

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

print(dp[N-1][W-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 j in range(N+1)]

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

Solution (Python):
import numpy as np
N, W = map(int, input().rstrip().split(' '))
weight_array = np.zeros(W+1)

for _ in range(N):
  w, v = map(int, input().rstrip().split(' '))
  weight_array[w:] = np.maximum(weight_array[:-w]+v, weight_array[w:])
print(int(weight_array[-1]))