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())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

def maxvalue_recursive(N, W):
    def memoize(func):
        func.d = d = {}
        def _f(*va):
            if va not in d: d[va] = func(*va)
            return d[va]
        return _f

    @memoize
    def maxvalue(i, w):
        if i < 0: return 0
        if w < ws[i]:
            return maxvalue(i - 1, w)
        else:
            return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

    res = maxvalue(N - 1, W)
    return res

def maxvalue_dp(N, W, ws, vs):
    import numpy as np
    dp = np.zeros(W + 1, 'int64')
    ws = np.array(ws, 'int64')
    vs = np.array(vs, 'int64')
    for i in range(N):
        idx = np.arange(W + 1) - ws[i]
        dp = np.maximum(dp, (dp[idx] + vs[i]) * (idx >= 0))
    return dp[-1]


print(maxvalue_dp(N, W, ws, vs))

Solution (Python):
import numpy as np

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

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

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

print(dp[W])

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

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

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: 0}
for i in range(N):
    for cw, cv in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cw + w[i]] = max(
            dp.get(cw + w[i], 0),
            cv + v[i])
print(max(dp.values()))

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

for _ in range(N):
    a, b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)

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

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

print(dp[N][W])

Solution (Python):
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.zeros(W + 1, dtype=np.int64)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])

Solution (Python):
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.zeros(W + 1, dtype=int)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])

Solution (Python):
import sys
N, W = map(int, input().split())
dp = [0] * (W + 1)
for weight, value in map(lambda x: map(int, x.split()), sys.stdin):
    for w in range(W - weight, -1, -1):
        if dp[w + weight] < dp[w] + value:
            dp[w + weight] = dp[w] + value
print(dp[-1])

Solution (Python):
import sys
LI = lambda: list(map(int, sys.stdin.readline().split()))
N, W = LI()
dp = [0] * (W + 1)
for weight, value in sorted(LI() for _ in range(N)):
    for w in range(W - weight, -1, -1):
        if dp[w + weight] < dp[w] + value:
            dp[w + weight] = dp[w] + value
print(dp[-1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = sorted([LI() for _ in range(n)])
    r = [0] * (w+1)
    mx = 0
    for a,b in aa:
        mx += a
        for i in range(min(mx, w-a),-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


print(main())

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

Solution (Python):
import sys
raw_input = sys.stdin.readline
N,W = map(int,raw_input().split())
dp = [0 for x in range(W+1)]
for i in range(N):
    a,b = map(int,raw_input().split())
    for j in range(W,a-1,-1):
        dp[j] = max(dp[j],dp[j-a]+b)
print max(dp)

Solution (Python):
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))

Solution (Python):


import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]


dp = [0] * (W + 1)
for weight, value in L:
    for w in range(W + 1)[::-1]:
        if w - weight < 0:
            continue
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[W])

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


if __name__ == "__main__":
    main()

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

print(dp[-1])

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

weight = [None] * N
value  = [None] * N

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

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

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

print(max(dp[N]))

Solution (Python):
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

dp=[[0 for x in range(wgt+1)] for x in range(n+1)]

for i in range(n+1):
    for j in range(wgt+1):
        if i==0 or j==0:
            dp[i][j]=0
        elif a[i-1]<=j:
            dp[i][j]=max(v[i-1]+dp[i-1][j-a[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][wgt])

Solution (Python):
N,W=[int(x) for x in raw_input().split()]
A=[]
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
B=[[ 0  for i in range(W+1)] for j in range(N)]
B[0][W-A[0][0]]=A[0][1]

for i in range(1,N):
    w,v=A[i]
    for j in range(W-w+1):
        B[i][j]=max(B[i-1][j], B[i-1][j+w]+v)
    for j in range(W-w+1, W+1):
        B[i][j]=B[i-1][j]
print(max(B[-1]))

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

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

print(dp[i][W])

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

append = items.append
for i in range(n):
    append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0] * (w + 1) for _ in range(n + 1)]
    g = [[0] * (w + 1) for _ in range(n + 1)]

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

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)

Solution (Python):

from sys import stdin
import numpy as np

ds_in = lambda: list(map(int, stdin.readline().split()))  


N, W = ds_in()

values = np.zeros(W + 1, dtype=int)  
for _ in range(N):
    pre = values.copy()
    wv = ds_in()  
    values[wv[0]:] = np.maximum(values[:-wv[0]] + wv[1], values[wv[0]:])

print(values[-1])

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

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

MAX = W
dp = [0]*(MAX+1)

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1-w)):
        if k + w > MAX:
            break
        else:
            dp[k+w] = max(dp[k+w], dp[k] + v)
print(max(dp))

Solution (Python):
a,b = map(int,input().split())

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

for i in range(a):
	w,h = map(int,input().split())
	for j in range(b,w-1,-1):
		dp[j] = max(dp[j],dp[j-w] + h)

print(max(dp))

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

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

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

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


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

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

    ans1 = f(N, W, wv)
    ans2 = simple(N, W, wv)

    

    print(ans2)


def simple(N, W, wv):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, 1):
        for _w in range(1, W + 1):
            bef = dp[i-1][_w]
            dp[i][_w] = bef

            
            if _w - w >= 0:
                changed = dp[i-1][_w - w] + v
                dp[i][_w] = max(bef, changed)

    ans = dp[N][W]
    return ans


def f(N, W, wv):
    """
    品物100を入れる入れないの 2^100 試せばOKだが、無理

    Nの入れる個数
        0から100
        正確にはN個までの選択なので、N個入れていないときもある
    最終容量     
        0から10^5
        正確にはWまでの重さなので、W以下のときもある
    10^7なら間に合いそう

    追加できるならば、追加してみる
    追加するものと入れ替えを試してみる
        追加の重さを引いたときの価値
        前の価値まま
            の大きい方
    """
    dp = [[-float("inf")] * (W + 1)
          for _ in range(N + 1)]

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

    for i, (w, v) in enumerate(wv, 1):
        for _w in range(1, W + 1):
            
            bef = dp[i-1][_w]
            dp[i][_w] = bef

            
            
            
            if _w + w <= W:
                changed = dp[i-1][_w] + v
                bef = dp[i-1][_w + w]
                
                

            
            if _w - w >= 0:
                changed = dp[i-1][_w - w] + v
                bef = dp[i-1][_w]
                dp[i][_w] = max(bef, changed)

    
    
    ans = dp[N][W]

    
    
    
    return ans


if __name__ == "__main__":
    main()

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

    ans = f(N, W, wv)
    print(ans)


def f(N, W, wv):
    """
    品物100を入れる入れないの 2^100 試せばOKだが、無理

    Nの入れる個数
        0から100
        正確にはN個までの選択なので、N個入れていないときもある
    最終容量     
        0から10^5
        正確にはWまでの重さなので、W以下のときもある
    10^7なら間に合いそう

    追加できるならば、追加してみる
    追加するものと入れ替えを試してみる
        追加の重さを引いたときの価値
        前の価値まま
            の大きい方
    """
    dp = [[-float("inf")] * (W + 1)
          for _ in range(N + 1)]

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

    for i, (w, v) in enumerate(wv, 1):
        for _w in range(1, W + 1):
            
            bef = dp[i-1][_w]
            dp[i][_w] = bef

            
            
            
            if _w + w <= W:
                changed = dp[i-1][_w] + v
                bef = dp[i-1][_w + w]
                
                

            
            if _w - w >= 0:
                changed = dp[i-1][_w - w] + v
                bef = dp[i-1][_w]
                dp[i][_w] = max(bef, changed)

    
    
    ans = dp[N][W]

    
    
    
    return ans


if __name__ == "__main__":
    main()

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

Solution (Python):
N, W = map(int, input().split())
wlst = []
vlst = []
for _ in range(N):
  w, v = map(int, input().split())
  wlst.append(w)
  vlst.append(v)
dp = [0] * (W + 1)
for w, v in zip(wlst, vlst):
  for i in range(W - w, -1, -1):
    dp[i + w] = max(dp[i + w], dp[i] + v)
print(dp[W])

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

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

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

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


N, W = [int(elem) for elem in fin().split()]
weight_value_pairs = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N))

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

print(max(dp))

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

Solution (Python):
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))

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

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

print(dp[W])

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

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

dp = [{} for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = src[i-1]
    for w0,v0 in dp[i-1].items():
        if w0 in dp[i]:
            dp[i][w0] = max(dp[i][w0], v0)
        else:
            dp[i][w0] = v0
        if w0+w > W: continue
        if w0+w in dp[i]:
            dp[i][w0+w] = max(dp[i][w0+w], v0+v)
        else:
            dp[i][w0+w] = v0+v
print(max(dp[-1].values()))

Solution (Python):
N, W = map(int, raw_input().split())
obj = []
for i in xrange(N):
    w, v = map(int, raw_input().split())
    obj.append((w, v))
dp = [[-1 for _ in xrange(W+1)] for i in xrange(N)]

dp[0][0] = 0
dp[0][obj[0][0]] = obj[0][1]

for i in xrange(1, N):
    w, v = obj[i]
    for j in xrange(W+1):
        if dp[i-1][j] != -1:
            dp[i][j] = dp[i-1][j]
    for j in xrange(W+1):
        if dp[i-1][j] != -1 and j + w <= W:
            dp[i][j+w] = max(dp[i-1][j]+v, dp[i][j+w])
res = 0
for i in xrange(W+1):
    res = max(dp[N-1][i], res)
print res

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

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

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

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

print(dp[N][W])

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

N, L = inpl()
DP = [0]*(L+1)
for i in range(N):
    DP2 = [0]*(L+1)
    w, v = inpl()
    for i in range(w):
        DP2[i] = DP[i]
    for j in range(L-w+1):
        DP2[j+w] = max(DP[j] + v, DP2[j+w-1], DP[j+w])
    DP = DP2
print(DP2[-1])

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

main()

Solution (Python):
import sys

n, W = map(int, input().split())
dp = [-1] * (W + 1)
dp[0] = 0
for line in sys.stdin.readlines():
    w, v = map(int, line.split())
    for i in range(W - w, -1, -1):
        if dp[i] == -1:
            continue
        dp[i + w] = max(dp[i + w], dp[i] + v)
print(max(dp))

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

DP_W=[0]*(W+1)

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

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

print(dp[N][W])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,w = li()
wv = []
for _ in range(n):
    wv.append(tuple(li()))
    
dp = [[0]*(w+1) for _ in range(n+1)]

for item in range(n):
    wi,vi = wv[item]
    for weight in range(w+1):
        if weight - wi >= 0:
            dp[item+1][weight] = max(dp[item][weight],
                                     dp[item][weight-wi] + vi)
            
        else:
            dp[item+1][weight] = dp[item][weight]
            
            
print(dp[n][w])

Solution (Python):
from collections import defaultdict
 
N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
 
dp = defaultdict(int)
 
dp[0] = 0
 
for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

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

Solution (Python):
n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)