Problem:
Knapsack Problem You have N kinds of items that you want to put them into a knapsack. Item i has value v i and weight w i . You want to find a subset of items to put such that:  The total value of the items is as large as possible.  The items have combined weight at most W , that is capacity of the knapsack.  You can select as many items as possible into a knapsack for each kind.  Find the maximum total value of items in the knapsack. Input  N  W  v 1  w 1  v 2  w 2 : v N  w N  The first line consists of the integers N and W . In the following lines, the value and weight of the i -th item are given. Output Print the maximum total values of the items in a line. Constraints  1 ≤ N ≤ 100  1 ≤ v i ≤ 1000  1 ≤ w i ≤ 1000  1 ≤ W ≤ 10000  Sample Input 1 4 8
4 2
5 2
2 1
8 3 Sample Output 1 21 Sample Input 2 2 20
5 9
4 10 Sample Output 2 10 Sample Input 3 3 9
2 1
3 1
5 2 Sample Output 3 27

Solution (Python):
N,W = map(int, input().split())
dp = [0 for i in range(W+1)]
for i in range(N):
	a,b = map(int,input().split())
	for j in range(b,W+1):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp[j] = x

print(max(dp))

Solution (Python):
def solve_knapsack(s, n, v, w):
	dp = [[0 for x in range(s+1)] for x in range(n+1)]	
	for i in range(n):
		for j in range(1, s+1):
			if w[i] > j:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = max(dp[i][j], max(dp[i+1][j-w[i]]+v[i], dp[i][j-w[i]]+v[i]))
	return dp[n][s]
	
n, s = map(int, input().split())
v = [0]*n
w = [0]*n
for i in range(n):
	v[i], w[i] = map(int, input().split())
print(solve_knapsack(s, n, v, w))

Solution (Python):



import sys
fin = sys.stdin.readline
N, W = [int(elem) for elem in fin().split()]
items = [[int(elem) for elem in fin().split()] for _ in range(N)]


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

for i in reversed(range(N)):
    for j in range(W + 1):
        value, weight = items[i]
        if j < weight:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = max(dp[i + 1][j],
                           dp[i + 1][j - weight] + value,
                           dp[i][j - weight] + value)

print(dp[0][W])

Solution (Python):
N,W=map(int,input().split())
goods=[tuple(map(int,input().split())) for _ in range(N)]
goods.sort(key=lambda x:x[0]/x[1],reverse=True)
dp=[0 for w in range(W+1)]
minw=W
for i in range(N):
    if i==0 or (goods[0][0]/goods[0][1]==goods[i][0]/goods[i][1] and minw>W%goods[i][1]):
        for j in range(W+1):
            dp[j]=goods[i][0]*(j//goods[i][1])
        minw=W%goods[i][1]
        roop=goods[i][1]
        continue
    for k in range(1+roop):
        weight=minw+roop*k
        if weight>W:
            for w in range(goods[i][1],1+W):
                dp[w]=max(dp[w-goods[i][1]]+goods[i][0],dp[w])
            break
        if weight%goods[i][1]==0:
            for w in range(W-weight,1+W):
                if w-goods[i][1]<0:continue
                dp[w]=max(dp[w-goods[i][1]]+goods[i][0],dp[w])
print(dp[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 (N):
    dp[i][0] =0
for j in range (W+1):
    dp[0][j] =0
    

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


print(dp[N][W])

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

for i in range(N):
    v_temp,w_temp=list(map(int,input().split()))
    value.append(v_temp)
    weight.append(w_temp)


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

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

Solution (Python):
import copy
length, cap = map(int, input().split(" "))
dp = [0] * (cap + 1)
items = []
for _ in range(length):
    a, b = map(int, input().split(" "))
    items.append([a, b])

for item in items:
    v, w = item
    temp_dp = copy.copy(dp)
    temp_dp[w] = max(temp_dp[w], v)
    for j in range(cap):
        if temp_dp[j] and w + j <= cap:
            temp_dp[w + j] = max(temp_dp[w + j], v + temp_dp[j])
    dp = temp_dp
answer = max(dp)
print(answer)

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

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

print(dp[W])

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

Solution (Python):
import sys

def knappack(N, W, vs, ws):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(ws[i], W + 1):
            dp[j] = max(dp[j], dp[j - ws[i]] + vs[i])
            
    return dp[-1]
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    Nstr, Wstr = line.split()
    N, W = int(Nstr), int(Wstr)
    vs, ws = [], []
    for i in range(N):
        line = sys.stdin.readline()
        v, w = line.split()
        v, w = int(v), int(w)
        vs.append(v)
        ws.append(w)
    sys.stdout.write(str(knappack(N, W, vs, ws)))
    sys.stdout.write('\n')

Solution (Python):
from sys import stdin
import operator

readline = stdin.readline


n, total_wait = map(int, readline().split())
value_wait = [list(map(int, readline().split())) for _ in range(n)]
value_wait.sort(key=operator.itemgetter(1), reverse=True)

dp = [0] * (total_wait + 1)

for ni, (v, w) in enumerate(value_wait):
    for tw in range(w, total_wait + 1):
        if dp[tw] < dp[tw - w] + v:
            dp[tw] = dp[tw - w] + v
print(dp[-1])

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

Solution (Python):



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

for j in range(1, N+1):
    v[j], w[j] = map(int,input().split())

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

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

print(dp[N][W])

Solution (Python):
n, w = map(int, raw_input().split())
dp = [0] * (w+1)
for _ in range(n):
    v, tw = map(int, raw_input().split())
    dp[tw] = v
    for i in range(w+1):
        if dp[i] != 0 and i+tw <= w:
            dp[i+tw] = max(dp[i+tw], dp[i] + v)
print max(dp)

Solution (Python):
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C
"""
 
from __future__ import division
from sys import stdin, maxint

def knapsack(N, W, infos):
    dp = [0] * (W + 1)
    for i in range(N):
    	for j in range(infos[i][1], W + 1):
    		dp[j] = max(dp[j], dp[j - infos[i][1]] + infos[i][0])
    return dp[W]
 
if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
        v, w = map(int, stdin.readline().strip().split())
        infos.append((v, w))
    print(knapsack(N, W, infos))

Solution (Python):


from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import

def array2d(row, col, init = None):
    return [[init for _ in range(col)] for _ in range(row)]

N, W = map(int, input().split(" "))
v = []
w = []
for i in range(N):
    vi, wi = map(int, input().split(" "))
    v.append(vi)
    w.append(wi)

dpt = array2d(N + 1, W + 1)

def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i-1]:
        dpt[i][j] = dp(i-1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i-1, j), dp(i, j-w[i-1]) + v[i-1])
    return dpt[i][j]

for i in range(N + 1):
    for j in range(W + 1):
        dp(i, j)
print(dp(N, W))

Solution (Python):
N,W=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for i in xrange(N)]
dp=[[0]*(W+1) for _ in xrange(N+1)]
for i in xrange(N):
    for j in xrange(W+1):
        if vw[i][1]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j-vw[i][1]]+vw[i][0])
print(dp[N][W])

Solution (Python):
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] 
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
for i in range(N):
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            DP[j] = product_in
        else:
            DP[j] = DP[j]
print(DP[W])

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

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

for _ in range(n):
    v, w = map(int, input().split())
    for k in range(cap - w + 1):
        new_v = dp[k] + v
        if dp[k + w] < new_v:
            dp[k + w] = new_v

print(max(dp))

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

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

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

print(dp[N][W])

Solution (Python):
num,weight = (int(n) for n in input().split(" "))
query = []
for n in range(num):
    query.append([int(n) for n in input().split(" ")])
nap = [[0 for n in range(weight + 1)] for m in range(num + 1)]
query = sorted(query,key = lambda x:x[1],reverse = True)
for n in range(num):
    for w in range(weight + 1):
        if w == 0:
            continue
        elif w >= query[n][1]:
            nap[n + 1][w] = max(nap[n+1][w-query[n][1]] + query[n][0] ,nap[n][w-query[n][1]] + query[n][0] ,nap[n][w])

print(nap[num][weight])

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

Solution (Python):



"""
input:
3 9
2 1
3 1
5 2

output:
27
"""

import sys
from collections import namedtuple


def solve():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.value, item.weight
        for cp in range(w, real_cp + 1):
            dp[cp] = max(dp[cp], dp[cp - w] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

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

Solution (Python):

"""docstring"""


def arr2d(d1, d2, init=None):
    return [[init for i in range(d2)] for j in range(d1)]


def solve(N, W):
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())

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


def main():
    n, w = map(int, input().split())
    print(solve(n, w))


if __name__ == "__main__":
    main()

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

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

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

print(value[W])

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

gra = [0]*(W+1)

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

print(max(gra))

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C, C[item_w:]), start=item_w):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print(C[W])

solve()

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

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

dp = [0] * (W+1)

for i in range(N):
    item_v, item_w = map(int, readline().split())
    for w in range(W-item_w+1):
        if dp[w+item_w] < dp[w] + item_v:
            dp[w+item_w] = dp[w] + item_v

print(max(dp))

Solution (Python):
from collections import defaultdict


def main():
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        v, w = map(int, input().split())
        items.append((v, w))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        v, w = items[i][0], items[i][1]
        for j in range(W + 1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            if j + w < len(dp[0]):
                dp[i][j + w] = max(dp[i][j + w], dp[i][j] + v)

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

if __name__ == '__main__':
    main()

Solution (Python):

N, W = tuple(map(int, input().split()))
items = []
for _ in range(N):
    items.append(list(map(int, input().split())))

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

for item in items:
    for w in range(item[1], W+1):
        cost[w] = max(cost[w], cost[w-item[1]]+item[0])

print(cost[-1])

Solution (Python):
INF = 10 ** 12

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

items =[] * N

for i in range(N):
    v, w = map(int, input().split())
    items.append([v,w])

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

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

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

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

print(dp[N][W])

Solution (Python):
def solve():
    
    INF = 10 ** 12
    
    N, W = map(int, input().split())
    
    items =[] * N
    
    for i in range(N):
        v, w = map(int, input().split())
        items.append([v,w])
    
    dp = [[INF for i in range(W+1)] for j in range(N+1)]
    
    for i in range(W+1):
        dp[0][i] = 0
    
    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(1,N+1): 
        for j in range(1, W+1): 
            if j - items[i-1][1] >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i-1][1]] + items[i-1][0], dp[i][j - items[i-1][1]] + items[i-1][0])
            else:
                dp[i][j] = dp[i-1][j]
    
    print(dp[N][W])

if __name__ == '__main__':
    solve()

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp
"""
import sys
input = sys.stdin.readline


def solve_knapsack(weight, items):
    dp = [[0]*(weight+1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight+1):
            if item[1] <= w:
                dp[i+1][w] = max((item[0] + dp[i][w-item[1]]),  dp[i][w], (item[0] + dp[i+1][w-item[1]]))
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]


def main(args):
    N, W = map(int, input().split())
    items = [[]]
    for _ in range(N):
        items.append([int(x) for x in input().strip().split()])
    result = solve_knapsack(W, items)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp
AC
"""
import sys
input = sys.stdin.readline


def solve_knapsack(weight, items):
    dp = [[0]*(weight+1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight+1):
            if item[1] <= w:
                
                dp[i+1][w] = max(dp[i][w], (item[0] + dp[i+1][w-item[1]]))
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]


def main(args):
    N, W = map(int, input().split())
    items = [[]]
    for _ in range(N):
        items.append([int(x) for x in input().strip().split()])
    result = solve_knapsack(W, items)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

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

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

print(max(dp))

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

Solution (Python):

NW=input().split()

N=int(NW[0])
W=int(NW[1])

item= []
for i in range(N):
    item.append(list(map(int, input().split())))

C=[[0 for i2 in range(W+1)]for i1 in range(N+1)]

for i in range(1,N+1):
    for j in range(1,W+1):
        if j>=item[i-1][1]:
            if item[i-1][0] + C[i][j -item[i - 1][1]] > C[i - 1][j]:
                C[i][j] = item[i-1][0] + C[i][j - item[i - 1][1]]
            else:
                C[i][j] = C[i -1][j]
        else:
            C[i][j]=C[i-1][j]

print(C[N][W])

Solution (Python):

N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


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

print(DP[-1][-1])

Solution (Python):

N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(w, W+1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1])

Solution (Python):



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

dp = [-float('inf') for i in range(W+1)]
dp[0] = 0
max_w = 0
for w in range(W+1):
    for i in range(N):
        if w - ws[i] < 0 :
            continue
        dp[w] = max(dp[w], dp[w-ws[i]]+vs[i])
        max_w = max(max_w, dp[w])


print(max_w)

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

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

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

for i in range(n):
    for j in range(weights[i], w+1):
        dp[j] = max(dp[j], dp[j-weights[i]]+values[i])

print(dp[w])

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

for i in range(N):
    v1, w1 = map(int,input().split(' '))
    v.append(v1)
    w.append(w1)

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

print(dp[N][W])

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


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

print(dp[N][W])

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

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

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

print(dp[W])

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

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

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

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

for i in range(1, w+1):
    for j in range(1, n+1):
        v, w = items[j-1]
        if i - w < 0:
            table[i][j] = table[i][j-1]
        else:
            new_val = table[i-w][j] + v
            table[i][j] = new_val if new_val > table[i][j-1] else table[i][j-1]

print(table[-1][-1])

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

value = []
weight = []

for _ in range(n):
  vi, wi = map(int, input().split())
  value.append(vi)
  weight.append(wi)

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

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

print(dp[w])

Solution (Python):
n,w = map(int, input().split())
item = [list(map(int,input().split())) for i in range(n)]
dp = [0 for i in range(w+2)]
for i in range(w+1):
    for v in item:
        if i+v[1] <= w:
            dp[i+v[1]] = max(dp[i+v[1]], dp[i]+v[0])
print(dp[w])

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

DP = [0]*(W+1)
for i in range(N):
    weight = w[i]
    value = v[i]
    for sum_w in range(1, W+1):
        if sum_w - weight >= 0:
            DP[sum_w] = max(DP[sum_w], DP[sum_w - weight] + value)
print(DP[-1])

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

value = [0] * N
weight = [0] * N

for i in range(N):
    value[i] = li[i][0]
    weight[i] = li[i][1]
    
dp = [[0] * (W+10) for _ in range(N+10)]

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

print(dp[N][W])

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

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


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

Solution (Python):
import sys

input = sys.stdin.readline


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

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

    ans = max(dp)
    print(ans)


if __name__ == "__main__":
    main()

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

value, weight= [0]*N, [0]*N

for i in range(N):
    v, w = list(map(int, input().split()))
    value[i], weight[i] = v, w

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
"""
for i in range(N):
    for j in range(W+1):
        k = 0
        while k * weight[i] <= j:
            res1 = dp[i+1][j]
            res2 = dp[i][j - k*weight[i]] + k * value[i]
            dp[i+1][j] = max(res1, res2)
            k += 1
"""

for i in range(N):
    for j in range(W+1):
        if j < weight[i]:
            dp[i+1][j] = dp[i][j]
        else:
            res1 = dp[i][j]
            res2 = dp[i+1][j - weight[i]] + value[i]
            dp[i+1][j] = max(res1, res2)

print(dp[N][W])

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, W = MI()
    d = [[0 for i in range(W+1)] for j in range(N+1)]
    mylist = [LI() for i in range(N)]
    for i in range(N):
        vt, wt = mylist[i]
        for j in range(W+1):
            if wt > j:
                d[i+1][j] = d[i][j]
            else:
                d[i+1][j] = max(d[i][j], d[i+1][j-wt]+vt)
    print(d[N][W])
    
if __name__ == "__main__":
    main()

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

Solution (Python):
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  v, w = map(int, input().split())
  value.append(v)
  weight.append(w)
dp = [[-1]*(W+1) for _ in range(N+1)]
dp[0][0] = 0

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

print(max(dp[N]))

Solution (Python):


n, max_weight = list(map(int, input().split(" ")))

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

items = [0 for _ in range(10**7)]
weights = []
for _ in range(n):
    v, w = list(map(int, input().split(" ")))
    if w not in weights:
        weights.append(w)
    items[w] = max(items[w], v)


for i in range(1, max_weight+1):
    for w in weights:
        if i >= w:
            dp[i] = max(dp[i-w] + items[w], dp[i])

print(dp[max_weight])

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

Solution (Python):
n,W=[int(x) for x in input().split()]

t=[0 for i in range(W+1)]

for i in range(n):
  v,w=[int(_) for _ in input().split()]
  
  for j in range(W-w+1):
    t[j+w]=max(t[j]+v,t[j+w])
print(max(t))

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





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

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

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

dp=[0 for j in range(www+1)]


for i in range(n):
    dpp = dp[:]
    for j in range(www+1):
        if (w[i] > j): continue
        dpp[j] = max(dpp[j],dpp[j-w[i]] + v[i])
    dp = dpp[:]

print(dp[www])

Solution (Python):
def main():
    import sys

    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    v, w = [], []
    for _ in [0] * N:
        a, b = map(int, readline().split())
        v.append(a)
        w.append(b)

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


main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

if __name__ == '__main__':
    main()

Solution (Python):
N,W = map(int,input().split())
Value = []
weight = []
inf=float("inf")
dp=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    v,w = map(int,input().split())
    Value.append(v)
    weight.append(w)


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

print(dp[N][W])

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

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

print(dp[-1])

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

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

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

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

dp = [0] * (W+1)

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

Solution (Python):
from pprint import pprint
n,w=map(int,input().split())
V=[]
W=[]
for _ in range(n):
    x,y=map(int,input().split())
    V.append(x)
    W.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],dp[i+1][j-W[i]]+V[i])
            

print(dp[n][w])