CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
Knapsack1
@author: maezawa
"""

n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,w+1):
        jw = j-warr[i]
        if jw <0:
            continue
        dp[i][j] = max([dp[k][jw] + varr[i] for k in range(i)])
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        
print((dp[n][w]))

# Optimized solution

n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,w+1):
        jw = j-warr[i]
        if jw <0:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = max(dp[i-1][jw] + varr[i], dp[i-1][j])
        
print((dp[n][w]))
# Original solution
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = list(map(int, input().rstrip().split()))
    item_list = []
    for _ in range(N):
        w, v = list(map(int, input().rstrip().split()))
        item_list.append((w, v))

    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値
    dp = [[0] * (W + 1) for _ in range(N)]

    for i, item in enumerate(item_list):
        for w in range(W+1):
            # もし品物iが入れられる
            if w + item[0] <= W:
                dp[i][w+item[0]] = max(dp[i][w+item[0]], dp[i-1][w]+item[1])
            # 入れないパターン
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    print((dp[N-1][W]))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = list(map(int, input().rstrip().split()))
    item_list = []
    for _ in range(N):
        w, v = list(map(int, input().rstrip().split()))
        item_list.append((w, v))

    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値
    dp = [[0] * (W + 1) for _ in range(N+1)]

    for i, item in enumerate(item_list, 1):
        for w in range(W+1):
            # もし品物iが入れられる
            if w + item[0] <= W:
                dp[i][w+item[0]] = max(dp[i][w+item[0]], dp[i-1][w]+item[1])
            # 入れないパターン
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    print((dp[N][W]))

if __name__ == '__main__':
    main()
# Original solution

N,W = list(map(int,input().split()))
lis = [[[0,0]]]

for i in range(N):

    w,v = list(map(int,input().split()))

    new = []

    for j in lis[i]:

        if j[0] + w <= W:

            new.append([j[0] + w , j[1] + v])
            
        new.append([j[0] ,j[1]])

    lis.append(new)

ans = 0

for i in lis[-1]:

    ans = max( ans , i[1] )

print (ans)


# Optimized solution

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

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = list(map(int,input().split()))

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print((lis[-1][W]))
# Original solution
N, W = list(map(int, input().split()))
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0]*(10**5 + 10) for _ in range(110)]

#i個の品物を入れて重さがjになっているときの価値の総和の最大値
#dp[i+1][j] = dp[i][j - w[i] + v[i]] 入れるとき
#dp[i+1][j] = dp[i][j] 入れないとき

#dp[0][j] = 0 初期値設定でOK
for i in range(N+1):
    for j in range(W+1):
        dp[i+1][j] = chmax(dp[i+1][j], dp[i][j])
        if (i < N):
            if (j >= w[i]):
                dp[i+1][j] = chmax(dp[i+1][j], dp[i][j - w[i]] + v[i])

print((dp[N][W]))

# Optimized solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)] #1-index

def chmax(a,b):
    if a >= b:
        return a
    else:
        return b
# dp[i+1][w]: i番目までの品物を選びその重さがwを超えないときの最大価値
dp = [[0]*(W+10) for _ in range(N+10)]

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

print((dp[N][W]))
# Original solution
import sys
input = sys.stdin.readline

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

def ans(N, W, wv):
    d = [[0] * (W+1) for i in range(N+1)]

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

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


# Optimized solution
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)))
# Original solution
N, W = [int(_) for _ in input().split()]
WV = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            reverse=True)
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print((max([v for k, v in list(dp.items())])))


# Optimized solution
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print((max([v for k, v in list(dp.items())])))
# Original solution
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
dp = [[0] * (w + 1) for _ 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(1, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print((dp[n][w]))

# Optimized solution
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
dp = [[0] * (w + 1) for _ 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(0, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print((dp[n][w]))
# Original solution
def main():
    N, W = list(map(int, input().split()))
    wi, vi = list(map(int, input().split()))
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = list(map(int, input().split()))
        dp[wi:] = [max(i + vi, j) for i, j in zip(dp, dp[wi:])]
    print((dp[-1]))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, W = list(map(int, input().split()))
    wi, vi = list(map(int, input().split()))
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = list(map(int, input().split()))
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print((dp[-1]))


if __name__ == '__main__':
    main()
# Original solution
n, w = list(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選べる場合、前の行からsum_wから品物iの重さを引いた要素を参照する
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])
        else:
            dp[i][j] = dp[i - 1][j]

print((max(max(dp))))

# Optimized solution
n, w = list(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選ばない場合で更新してから、選べる場合は再更新
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])

print((dp[n][w]))
# Original solution


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    
    N, W = list(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)))

if __name__ == '__main__':
    main()
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    
    N, W = list(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)))

if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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

if __name__ == '__main__':
    main()
# Original solution
N, W = list(map(int, input().split()))
X = [0] + [-1] * W

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

print((max(X)))

# Optimized solution
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 = list(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 = list(map(int, input().split()))
    s = MAX(s, (s >> w * K) + one * v)

print((max(tolist(s)) - (1 << K - 2)))
# Original solution
n,w=list(map(int,input().split()))
l=[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 sum_w in range(w+1):
        
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #l[i]を入れるとき
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
        #入れない時
print((dp[-1][-1]))


# Optimized solution
#DP-C

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

print((max(dp[-1])))
# Original solution
N,W = list(map(int,input().split()))
dp = [0 for _ in range(W+1)]
for i in range(N):
    w,v = list(map(int,input().split()))
    for j in range(W+1):
        if j+w <= W:
            dp[j] = max(dp[j],dp[j+w]+v)
print((max(dp)))

# Optimized solution
N, capW = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]
 
def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(list(range(wi, capW+1))):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)
 
print((knapsack01(items, capW)))
# Original solution
import sys

input = sys.stdin.readline


def main():
    N, W = list(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 sum_w in range(W+1):

            if sum_w - wv[i][0] >= 0:
                DP[i+1][sum_w] = max(
                    DP[i][sum_w - wv[i][0]] + wv[i][1],
                    DP[i+1][sum_w])

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

    print((DP[N][W]))


if __name__ == '__main__':
    main()


# Optimized solution
import sys

def main():
    _input = sys.stdin.readline

    N, W = list(map(int, _input().split()))
    wv = [list(map(int, _input().split())) for _ in range(N)]

    wv.sort()

    DP = [-1] * (W+1)
    DP[0] = 0

    sum_w = 0
    for w, v in wv:
        sum_w += w
        for j in range(min(W, sum_w), w-1, -1):
            if DP[j-w] == -1:
                continue
            if DP[j] < DP[j-w] + v:
                DP[j] = DP[j-w] + v
    print((max(DP)))


if __name__ == '__main__':
    main()
# Original solution
N, W = list(map(int, input().split()))

dp = [0] * (W + 1)
weights2check = [0]
for _ in range(N):
    w, v = list(map(int, input().split()))
    new_weights2check = []
    for k in weights2check:
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            new_weights2check.append(k + w)

    weights2check += new_weights2check


ans = max(dp[i] for i in weights2check)
print(ans)

# Optimized solution
N, W = list(map(int, input().split()))

dp = [0] * (W + 1)
weights2check = [0]
ans = 0
for _ in range(N):
    w, v = list(map(int, input().split()))
    for k in range(W-w, -1, -1):
        dp[k + w] = max(dp[k + w], dp[k] + v)
        ans = max(ans, dp[k + w])


print(ans)
# Original solution
N,W=list(map(int,input().split()))
wv=[list(map(int,input().split())) for i in range(N)]

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

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

print((dp[N][W]))

# Optimized solution
N, W = list(map(int, input().split()))
wv = [[int(i) for i in input().split()] for i in range(N)]
 
dp=[[0]*(W+1) for i in range(N+1)]
 
for w in range(W+1):
    for n in range(N):
        if wv[n][0] <= w:
            dp[n+1][w] = max(dp[n][w-wv[n][0]] + wv[n][1], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
 
 
print((dp[N][W]))
# Original solution
N,W=list(map(int,input().split()))
wv=[list(map(int,input().split())) for _ in range(N)]

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


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

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


# Optimized solution
N,W=list(map(int,input().split()))
w=[0]*N
v=[0]*N

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

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

for i in range(W+1):
    for g in range(N):
        if i>=w[g]:
            dp[g+1][i]=max(dp[g][i],v[g]+dp[g][i-w[g]])
        else:
            dp[g+1][i]=dp[g][i]
print((dp[N][W]))
# Original solution
n,W=list(map(int,input().split()))
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=list(map(int,input().split()))
    w_list.append(w)
    v_list.append(v)
for i in range(n):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
dp_sub=[]
for j in range(W+1):
    dp_sub.append(0)
dp.append(dp_sub)
for i in range(n):
    i_=n-1-i
    for j in range(W+1):
        if w_list[i_]<=j:
            dp[i_][j]=max(dp[i_+1][j],dp[i_+1][j-w_list[i_]]+v_list[i_])
        else:
            dp[i_][j]=dp[i_+1][j]
print((dp[0][W]))




# Optimized solution
n,W=list(map(int,input().split()))
w_list=[0]
v_list=[0]
for i in range(n):
    w,v=list(map(int,input().split()))
    w_list.append(w)
    v_list.append(v)
dp=[]
for i in range(n+1):
    sub_list=[]
    for j in range(W+1):
        sub_list.append(0)
    dp.append(sub_list)
for i in range(1,n+1):
    for j in range(W+1):
        if j>=w_list[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_list[i]]+v_list[i])
        else:
            dp[i][j]=dp[i-1][j]
print((dp[n][W]))
# Original solution
N,W = list(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)


# Optimized solution
n,w = list(map(int,input().split()))
dp = [[0]*(w+1) for i in range(n+1)]

for i in range(1, n+1) :
    a, v = list(map(int,input().split()))
    for j in range(1, w+1) :
        if j < a :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        else :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-a]+v)

print((dp[n][w]))
# Original solution
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    #dp = [[0]*(W+1) for _  in range(N+1)]
    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]))
解()


# Optimized solution
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]))
解()
# Original solution
N, W = list(map(int, input().split(' ')))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print((dp[-1][-1]))

# Optimized solution
N, WW = list(map(int, input().split()))
W = [0] * N
V = [0] * N
for i in range(N):
    w, v = list(map(int, input().split()))
    W[i] = w
    V[i] = v
dp = [[0]*(WW+1) for _ in range(N+1)]
for n in range(1, N+1):
    w = W[n-1]
    v = V[n-1]
    for sum_w in range(WW+1):
        if sum_w <= WW - w:
            # n番目の商品を選ぶ
            dp[n][sum_w+w] = max(dp[n-1][sum_w] + v, dp[n][sum_w+w])
        dp[n][sum_w] = max(dp[n-1][sum_w], dp[n][sum_w])
print((dp[-1][-1]))
# Original solution
def LI(): return [int(x) for x in input().split()]
def II(): return int(eval(input()))

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

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

for i,(w,v) in enumerate(LIS, 1):
    for wb in range(0, W+1):
        DP[i][wb] = DP[i-1][wb]
        if wb >= w :
            DP[i][wb] = max(DP[i][wb], DP[i-1][wb-w]+v)
# for lis in DP:
#     print(lis)

print((DP[N][W]))


# Optimized solution
def LI(): return [int(x) for x in input().split()]
def II(): return int(eval(input()))

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

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

for i,(w,v) in enumerate(LIS, 1):
    for wb in range(0, W+1):
        DP[i][wb] = DP[i-1][wb]
        if wb >= w :
            DP[i][wb] = max(DP[i][wb], DP[i-1][wb-w]+v)

print((DP[N][W]))
# Original solution
def MAP(): return list(map(int,input().split()))
def INT(): return int(eval(input()))
def FLOAT(): return float(eval(input()))
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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] = 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]))

# Optimized solution
n,W = list(map(int,input().split()))
w = []
v = []
for i in range(n):
    w_,v_ = list(map(int,input().split()))
    w.append(w_)
    v.append(v_)

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

print((dp[n][W]))
# Original solution
n,w=list(map(int,input().split()))
d,f=list(map(int,input().split()))
if n==1:print((f if d<=w else 0));exit()
dp=[[0,0],[d,f]]#w,v
dp_=[]
for i in range(1,n):
  d,f=list(map(int,input().split()))
  if dp_==[]:
    for x,c in dp:
      if x+d<=w:dp_.append([x+d,c+f])
    dp_+=dp
    dp=[]
  else:
    for x,c in dp_:
      if x+d<=w:dp.append([x+d,c+f])
    dp+=dp_
    dp_=[]
print((max(sum(dp+dp_,[])[1::2])))

# Optimized solution
n,w=list(map(int,input().split()))
dp=[0]*(w+1)
for i in range(n):
    wi,vi=list(map(int,input().split()))
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print((dp[-1]))
# Original solution
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd = [[0 for _ in range(W+1)] for k in range(n+1)]

for i in range(n):
	w,v=list(map(int,input().split()))
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[i][w]!=0:
		
		return dd[i][w]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[i][w]=c
	return c
print((maxv(0,0)))



# Optimized solution
n,W=list(map(int,input().split()))
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=list(map(int,input().split()))
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print((dp[W]))
# Original solution
n,W=list(map(int,input().split()))
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=list(map(int,input().split()))
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print((dp[W]))

# Optimized solution
n,W=list(map(int,input().split()))
dp=[0]*(W+1)
for i in range(n):
	w,v=list(map(int,input().split()))
	for j in range(W,-1,-1):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dp[cw]<cv:
			dp[cw]=cv
print((dp[W]))