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):
import sys
import numpy as np


input = sys.stdin.readline


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

def knapsack(n, w):
    
    dp = np.zeros([N+1, W+1], dtype='int64')
    
    for i in range(N):
        w, v = map(int, input().split())
        
        dp[i+1][:w] = dp[i][:w]
        dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w] + v)
        
    return dp[-1][-1]

print(knapsack(N, W))

Solution (Python):

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

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

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

  for w, v in items:  
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
  res = max(dp)
  print(res)

if __name__ == "__main__":
  solve()

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

dp = [0]  * (W + 1)
def knapsack():
  for i in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
knapsack()
res = max(dp)
print(res)

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

dp = [0]  * (W + 1)
def knapsack():
  for i in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
  return max(dp)
print(knapsack())

Solution (Python):
def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))

Solution (Python):
import sys

input = sys.stdin.readline


def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))

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

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))

Solution (Python):

import numpy as np
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
value=np.zeros((n+1,w+1),dtype=int)
for i in range(n):
    wei=wv[i][0]
    value[i+1][:wei]=value[i][:wei]
    
    value[i+1][wei:]=np.maximum(value[i][wei:],value[i][:-wei]+wv[i][1])

print(value[n][w])

Solution (Python):
def solve():
    N, W = map(int, input().split())
    weight = [0 for i in range(N)]
    value = [0 for i in range(N)]
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    dp = [0 for w in range(W + 1)]

    for i in range(N):
        wi = weight[i]
        vi = value[i]
        for w in range(W, -1, -1):
            _w = w + wi
            _v = dp[w] + vi
            if _w > W: continue
            if _v <= dp[_w]: continue
            dp[_w] = _v
    return dp[-1]

print(solve())

Solution (Python):
import numpy as np

N, W = map(int, input().split())
wv = [[0, 0]] + [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N+1, W+1], dtype=int)

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

print(dp[N][W])

Solution (Python):
import math
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right


def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
INF = float("inf")

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

w, v = [], []
for _ in range(N):
    wi, vi = s_inpl()
    w.append(wi)
    v.append(vi)

for i in range(N):
    for sum_w in range(W+1):

        
        if sum_w >= w[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])

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

print(dp[N][W])

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

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

Solution (Python):
import numpy as np

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=np.zeros(w+1,dtype=np.int64)

for i in range(n):
    if l[i][0]<=w:
        dp[l[i][0]:w+1]=np.maximum(dp[0:w+1-l[i][0]]+np.array(l[i][1]),dp[l[i][0]:])
    
print(max(dp))

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

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

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()
dp = [[0]*(w+1) for _ in range(n+1)]

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

Solution (Python):
def main():
    N, W = [int(n) for n in input().split()]
    baggages = [[int(n) for n in input().split()] for i in range(N)]

    VALUE, WEIGHT = 1, 0
    dp = [[-1] * (W+1) for n in range(N)]
    
    dp[0] = [0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE] for weight in range(W+1)]

    for baggage in range(N):
        for max_weight in range(W+1):
            if dp[baggage][max_weight] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][max_weight]
            val2 = dp[baggage-1][max_weight-bag_w]+bag_v if max_weight >= bag_w else 0
            dp[baggage][max_weight] = max(val1, val2)
            
    print(dp[N-1][W])



if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
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 j in range(W+1):
        if w>j:
            DP[i+1][j]=DP[i][j]
        else:
            DP[i+1][j]=max(DP[i][j],DP[i][j-w]+v)
print(max(DP[-1]))

Solution (Python):
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

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

for i in range(w+1):
    maxa = 0
    useda = [0 for i in range(n)]
    for k in range(n):
        if used[i-weighs[k]][k] == 0 and i-weighs[k] >= 0 and dp[i-weighs[k]]+values[k]>maxa:
                maxa = dp[i-weighs[k]]+values[k]
                useda = used[i-weighs[k]][:]
                useda[k] = 1
    dp[i] = maxa
    used[i] = useda


print(max(dp))

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


def I():
    return 























if __name__ == '__main__':
    D()

Solution (Python):



import sys


N,W = map(int, sys.stdin.readline().rstrip().split())
w = [0] * N
v = [0] * N
for i in range(N):
  w[i], v[i] = list(map(int, sys.stdin.readline().rstrip().split()))

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

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

Solution (Python):
n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

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

print(dp[N][W])

Solution (Python):
import numpy as np
n,w=map(int,input().split())
a=np.zeros([n,w+1],dtype=int)
c,d=map(int,input().split())
a[0][c:]=d
for i in range(1,n):
    e,f=map(int,input().split())
    a[i][:e]=a[i-1][:e]
    a[i][e:]=np.maximum(a[i-1][e:],a[i-1][:-e]+f)
print(a[-1][-1])

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

Solution (Python):
import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

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

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

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

Solution (Python):
import sys
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

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

print(max(dp))

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

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

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [0] * (W+1)

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        for w in range(W, wi - 1, -1):
            v_ = d[w - wi] + vi
            if v_ > d[w]:
                d[w] = v_
    return d[W]

print(ans(N, W))

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

print(dp[n][w])

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

print(dp[n][w])

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

Solution (Python):


import sys
input = sys.stdin.readline

def f(n, W):
    dp = [0] * (W + 1)
    for i in range(n):
        wi, vi = map(int, input().split())
        for w in range(W, wi - 1, -1):
            v_ = dp[w - wi] + vi
            if dp[w] < v_:
                dp[w] = v_
    return(dp[-1])

n, w = map(int, input().split()) 
print(f(n, w))

Solution (Python):

import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) 

print(f(n, w))

Solution (Python):
def d_knapsack1(N, W, Goods):
    """
    N個の品物のi番目について、重さはw_i, 価値はv_iである。
    品物のいくつかを選んでナップサックに入れるが、品物の重さの総和はW以下とする。
    品物の価値の総和の最大値を求めよ。
    ※ 1 <= w_i <= W <= 10^5 と、重さの制約がゆるめ
    """
    import numpy as np
    
    dp = np.zeros(W + 1, dtype=np.int64)
    for w, v in Goods:
        
        
        np.maximum(dp[:W + 1 - w] + v, dp[w:], out=dp[w:])
        
    return dp[-1]

N, W = [int(i) for i in input().split()]
Goods = [[int(i) for i in input().split()] for j in range(N)]
print(d_knapsack1(N, W, Goods))

Solution (Python):

import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) 

print(f(n, w))

Solution (Python):
from sys import stdin
n,W=map(int,input().split())
dp=[0 for i in range(W+1)]
for i in range(n):
    w,v=map(int,stdin.readline().split())
    for j in range(W-w,-1,-1):
        dp[j+w]=max(dp[j]+v,dp[j+w])
print(dp[-1])

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

Solution (Python):
n, mw = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(mw+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(mw+1):
        w, v = goods[i]
        if j >= w:
            dp[i+1][j] = max(dp[i][j], dp[i][j - w] + v)
        else: dp[i+1][j] = dp[i][j]
print(dp[n][mw])

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

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

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

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

dp = [[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

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

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

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

print(dp[0][W])

Solution (Python):
import numpy as np
n, W = map(int, input().split())
dp = np.zeros(W+1,'i8')

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

Solution (Python):


"""
Created on 2019/3/2
Update on 2019/3/5
Solved on 2019/3/
@author: shinjisu
"""




import numpy as np


def getInt(): return int(input())



def getIntList(): return np.array(input().split(), dtype=np.longlong)



def zeros(n): return np.zeros(n, dtype=np.longlong)


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_A():  
    N = getInt()
    H = getIntList()
    dmp((N, H), 'N, H')
    c = zeros(N)
    c[1] = abs(H[1]-H[0])
    for i in range(2, N):
        c[i] = min(c[i-1] + abs(H[i]-H[i-1]),
                   c[i-2] + abs(H[i]-H[i-2]))
    dmp(c, 'c')
    return c[N-1]


def prob_B_TLE():  
    N, K = getIntList()
    H = getIntList()
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N)
    c[0] = 0
    for i in range(1, N):
        
        for j in range(max(0, i-K), i):
            c[i] = min(c[i], c[j] + abs(H[i]-H[j]))
    dmp(c, 'c')
    return c[N-1]


def prob_B():  
    N, K = getIntList()
    H = np.array(input().split(), dtype='int')
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N, dtype=np.longlong)
    c[0] = 0
    for i in range(1, N):
        c[i] = np.min(c[max(0, i-K):i] + np.abs(H[max(0, i-K):i] - H[i]))
    dmp(c, 'c')
    return c[N-1]


def prob_C():  
    N = getInt()
    a = zeros(N)
    b = zeros(N)
    c = zeros(N)
    for i in range(N):
        a[i], b[i], c[i] = getIntList()
    dmp(N, 'N')
    dmp(a, 'a')
    dmp(b, 'b')
    dmp(c, 'c')
    dpa = zeros(N)
    dpb = zeros(N)
    dpc = zeros(N)
    dpa[0] = a[0]
    dpb[0] = b[0]
    dpc[0] = c[0]
    for i in range(1, N):
        dpa[i] += max(dpb[i-1], dpc[i-1]) + a[i]
        dpb[i] += max(dpc[i-1], dpa[i-1]) + b[i]
        dpc[i] += max(dpa[i-1], dpb[i-1]) + c[i]
    dmp(dpa, 'dpa')
    dmp(dpb, 'dpb')
    dmp(dpc, 'dpc')
    return max(dpa[N-1], dpb[N-1], dpc[N-1])


def prob_D():  
    N, W = getIntList()
    w, v = zeros(N), zeros(N)
    dmp((N, W))
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp(w, 'weight')
    dmp(v, 'value')
    dp = zeros(W+1)
    dmp(dp.size)
    for i in range(N):
        dmp(dp, 'dp')
        dmp(w[i],'w[i]')
        
        
        dmp(w[i],'w[i]')
        dp[w[i]:] = np.maximum(dp[w[i]:], 
                                  dp[:W-w[i]+1] + v[i])
    dmp(dp, 'dp')
    return dp[W]


debug = False  
ans = prob_D()
print(ans)

Solution (Python):

import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

n, m = 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] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

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

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

Solution (Python):
import numpy as np 

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

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

print(w_all[W])

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

Solution (Python):

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



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

print(dp[N][W])

Solution (Python):


import numpy as np
import sys

N,W = map(int, sys.stdin.readline().rstrip().split())

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

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

print(dp[-1])

Solution (Python):
from sys import stdin
n,W=map(int,input().split())
k=[[0 for i in range(W+1)] for i in range(2)]
for i in range(1,n+1):
    w,v=map(int,stdin.readline().split())
    for j in range(1,W+1):
        if w<=j:
            k[1][j]=max(v+k[0][j-w],k[0][j])
        else:
            k[1][j]=k[0][j]
    k[0]=[i for i in k[1]]
    k[1]=[0]*(W+1)
print(k[0][-1])

Solution (Python):
from sys import stdin
n,W=map(int,input().split())
k=[[0 for i in range(W+1)] for i in range(n+1)]
for i in range(1,n+1):
    w,v=map(int,stdin.readline().split())
    for j in range(1,W+1):
        if w<=j:
            k[i][j]=max(v+k[i-1][j-w],k[i-1][j])
        else:
            k[i][j]=k[i-1][j]
print(k[n][W])

Solution (Python):
import numpy as np


def solve(w, items):
    dp = np.zeros(w + 1, dtype=int)

    for weight, value in items:
        dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)

    return dp[w]


def main():
    n, w = map(int, input().split())
    items = list(list(map(int, input().split())) for _ in range(n))

    ans = solve(w, items)
    print(ans)


main()

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

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

for i in range(N) :
    weight_i,value_i = L[i]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight], dp[i][weight - weight_i] + value_i)
        else :
            dp[i+1][weight] = dp[i][weight]

ans = dp[N][W]

print(ans)

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

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

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

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