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())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,w+1):
        if l[i-1][0]<=j:
            
            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[-1][-1])

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

print(max(dp[-1]))

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

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

for w in range(W+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if Wi <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w-Wi] + Vi)
        dp[n+1][w] = max(dp[n][w], dp[n+1][w])

print(dp[N][W])

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

Solution (Python):
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


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 lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


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

Solution (Python):
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,W = map(int,readline().split())
WV = [list(map(int,readline().split())) for _ in range(N)]

dp = np.zeros(W+1,np.int64)
for w,v in WV:
  np.maximum(dp[w:],dp[:-w].copy() +v,out=dp[w:])
print(dp.max())

Solution (Python):
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,W = map(int,readline().split())
WV = [list(map(int,readline().split())) for _ in range(N)]

dp = np.zeros(W+1,np.int64)
for w,v in WV:
  np.maximum(dp[w:],dp[:-w].copy() +v,out=dp[w:])
print(dp.max())

Solution (Python):


def MAX(a, b):
    d = a + ms - b
    return b + ((ms - ((d & ms) >> (K - 1))) & mask & d)

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
mask = int(("0" + "1" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = map(int, input().split())
    s = MAX(s, (s >> w * K) + one * v)

print(max(tolist(s)) - (1 << K - 2))

Solution (Python):


def MAX(a, b):
    d = a + ms - b
    return b + ((((d & ms) >> (K - 1)) * tt) & d)

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = map(int, input().split())
    s = MAX(s, (s >> w * K) + one * v)

print(max(tolist(s)) - (1 << K - 2))

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

N,W = map(int, readline().split())
w=[];v=[]
for _ in range(N):
  a,b = map(int, readline().split())
  w.append(a)
  v.append(b)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
  for j in range(W+1):
    if j >= w[i]:
      dp[i+1][j] = 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):
def MAX(a, b):
    return b + (((((a + ms - b) & ms) >> (K - 1)) * tt) & (ms + a - b))

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = map(int, input().split())
    s = MAX(s, (s >> w * K) + one * v)

print(max(tolist(s)) - (1 << K - 2))

Solution (Python):
def MAX(a, b):
    return b + (((((a + ms - b) & ms) >> (K - 1)) * tt) & (ms + a - b))
def MIN(a, b):
    return a - (((((a + ms - b) & ms) >> (K - 1)) * tt) & (ms + a - b))

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

a = 8
b = 39

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = map(int, input().split())
    s = MAX(s, (s >> w * K) + one * v)

print(max(tolist(s)) - (1 << K - 2))

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

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

for i in range(n):
	for j in range(k+1):
		if j-w[i] < 0:
			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][k])

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

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

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

print(max(dp[N]))

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

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

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

print(dp[N][W])

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

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

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

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

            
print(max(dp[N]))

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

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

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

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

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

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

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = dp[i-1][0]
    flag = dp[i-1][1]
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print(dp[W][0])

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

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

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

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

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

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

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

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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    
    
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

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

    print(dp[N][W])
    return


if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
ws = [0] * N
vs = [0] * N

for i in range(N):
  ws[i], vs[i] = map(int, input().split())

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

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i][w_now] = max( dp_table[i-1][w_now], dp_table[ i-1][w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i][w_now] = dp_table[i-1][w_now]
print(int(dp_table[-1][-1]))

Solution (Python):


import sys

def main2():
    n,k = map(int,(input().split()))
    items=[list(map(int,input().split())) for _ in range(n)]
    dp = [[0 for _ in range(k+1)] for _ in range(n)]
    for i in range(n):
        for j in range(k+1):
            if i==0 and j>=items[0][0]:
                dp[0][j]=items[0][1]
            elif i>0 and j>=items[i][0]:
                dp[i][j]=max(dp[i-1][j],items[i][1]+dp[i-1][j-items[i][0]])
            elif j < items[i][0] and i > 0:
                dp[i][j]=dp[i-1][j]
    print (dp[-1][-1])

if __name__ == "__main__":
    main2()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, W = map(int, readline().split())
    INF = int(1e5)+100
    weight = [0 for _ in range(110)]
    value = [0 for _ in range(110)] 
    for i in range(N):
        w, v = map(int, readline().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for _ in range(INF)] for _ in range(110)]
    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])
if __name__ == '__main__':
    main()

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


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

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

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

    return dp[-1][-1]


if __name__ == "__main__":
    print(main())

Solution (Python):
def chmax(dp, i, x):
  if dp[i] < x:
    dp[i] = x
    return True
  return False

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

Solution (Python):
def chmax(dp, i, x):
  if dp[i] < x:
    dp[i] = x
    return True
  return False

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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W + 1, dtype = np.int64)

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

print(dp[W])

Solution (Python):
import sys,io
from functools import lru_cache
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
N,W=reads()
weight,value=[0]*N,[0]*N
for i in range(N):
    weight[i],value[i]=reads()
dp=[[ 0 for _ in  range(W+1) ] for _ in range(N+1)]
for i in range(N):
  for k in range(W+1):
    if (k >= weight[i]) :dp[i+1][k] = max(dp[i][k-weight[i]] + value[i], dp[i][k])
    else :dp[i+1][k] = dp[i][k]
print("{}".format(dp[N][W]))

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

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

Solution (Python):
N, W = map(int, input().split())
a = list()
a.append([0, 0])
inf = float('inf')
for _ in range(N):
  x = list(map(int, input().split()))
  a.append(x)
dp = [[-inf for _ in range(W+1)]for _ in range(N+1)]

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

Solution (Python):
l=input().split()
n=int(l[0])
W=int(l[1])
lweight=[]
lvalue=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	lweight.append(u)
	lvalue.append(v)
dp=[[0 for i in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	dp[i][0]=0
for j in range(W+1):
	dp[0][j]=0
for i in range(1,n+1):
	for j in range(1,W+1):
		if(j>=lweight[i-1]):
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-lweight[i-1]]+lvalue[i-1])
		else:
			dp[i][j]=dp[i-1][j]
print(dp[n][W])

Solution (Python):
n, w = map(int, input().split())
W = [0] * n
V = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    W[i] = a
    V[i] = b


dp = [[0] * (10 ** 5 + 10) for _ in range(n + 10)]
for i in range(n):
    for sum_num in range(w + 1):
        if sum_num - W[i] >= 0:
            dp[i + 1][sum_num] = max(dp[i][sum_num - W[i]] + V[i], dp[i][sum_num])
        else:
            dp[i + 1][sum_num] = dp[i][sum_num]

print(dp[n][w])

Solution (Python):
import numpy as np
N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = np.zeros(shape=(N,W + 1),dtype = int)
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    weight = l[i][0]
    value = l[i][1]
    dp[i][:weight] = dp[i - 1][:weight]
    dp[i][weight:] = np.maximum(dp[i - 1][weight:], value + dp[i - 1][:-weight])
print(dp[N - 1][W])

Solution (Python):
def read_int():
    return int(input().strip())
 
 
def read_ints():
    return list(map(int, input().strip().split(' ')))
 
 
def solve():
    """
    OPT[N][W] = maximum value obtained with first N items and weights up to W
    OPT[N][W] = max(OPT[N-1][W-w[N]]+v[N], OPT[N-1][W])
    OPT[0][0] = 0
    """
    N, W = read_ints()
    w, v = [], []
    for _ in range(N):
        w0, v0 = read_ints()
        w.append(w0)
        v.append(v0)
    OPT = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,W+1):
            OPT[i][j]=OPT[i-1][j]
            if j-w[i-1]>=0:
                OPT[i][j]=max(OPT[i][j],OPT[i-1][j-w[i-1]]+v[i-1])
    return OPT[-1][-1]
if __name__ == '__main__':
    print(solve())

Solution (Python):
import numpy as np

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

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

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

for i in range(N):
    weight = items[i][0]
    value = items[i][1]
    dp[i + 1][:weight] = dp[i][:weight]
    dp[i + 1][weight:] = np.maximum(dp[i][weight:], value + dp[i][:-weight])

print(dp[N][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()

Solution (Python):


def read_int():
    return int(input().strip())


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


def solve():
    """
    OPT[N][W] = maximum value obtained with first N items and weights up to W
    OPT[N][W] = max(OPT[N-1][W-w[N]]+v[N], OPT[N-1][W])
    OPT[0][0] = 0
    """
    N, W = read_ints()
    w, v = [], []
    for _ in range(N):
        w0, v0 = read_ints()
        w.append(w0)
        v.append(v0)
    OPT = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, W+1):
            OPT[i][j] = OPT[i-1][j]
            if j-w[i-1] >= 0:
                OPT[i][j] = max(OPT[i][j], OPT[i-1][j-w[i-1]]+v[i-1])
    return OPT[-1][-1]


if __name__ == '__main__':
    print(solve())

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

Solution (Python):
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])

Solution (Python):
import math
import bisect
from queue import Queue
from collections import deque

n, w = [int(i) for i in input().split()]

nap = [[int(i) for i in input().split()] for j in range(n)]

dp = [[0 for _ in range(100001)] for _ in range(101)]

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

print(dp[n][w])

Solution (Python):
import sys
rl = sys.stdin.readline
def a():
    N, W = map(int, rl().split())
    dp = [-1]*(W+1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, rl().split())
        for i in range(W-w, -1, -1):
            dpi = dp[i]
            if dpi == -1:
                continue
            if dp[i+w] < dpi + v:
                dp[i+w] = dpi + v
    print(max(dp))
a()

Solution (Python):
import sys
rl = sys.stdin.readline
def a():
    N, W = map(int, rl().split())
    dp = [-1]*(W+1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, rl().split())
        for i in range(W-w, -1, -1):
            dpi = dp[i]
            if dpi == -1:
                continue
            if dp[i+w] < dpi + v:
                dp[i+w] = dpi + v
    print(max(dp))
a()

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

inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	
	
	
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
		
		
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Solution (Python):
import sys

inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	
	
	
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		dp[(i+1)%3] = [0]*(w+1)
		
		
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Solution (Python):
import sys

inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(n)]
	w_v_list = [read() for i in range(n)]
	
	
	
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i][j] = max(elem_v + dp[i-1][j - elem_w], dp[i][j-1], dp[i-1][j])
				
			else:
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
	
	print(dp[n-1][w])




if __name__ == "__main__":
	solve()

Solution (Python):
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.zeros(W+1,dtype=np.int64)
for w,v in wv:
    np.maximum(dp[w:],dp[:-w]+v,out=dp[w:])
print(dp.max())

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

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

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W+1, int)

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

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

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

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, W = map(int, input().split())
    dp = [-INF] * (W + 1)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for w0 in range(W, -1, -1):
            if dp[w0] == INF:
                continue
            if w + w0 <= W:
                dp[w + w0] = max(dp[w + w0], dp[w0] + v)
    print(max(dp))
resolve()