CodeEff/ECCO huggingface dataset:
# Original solution
def main():
  N, W = list(map(int, input().split()))
  dp = [-1] * (W + 1)
  dp[0] = 0
  ws = []
  ps = []
  for _ in range(N):
    w, v = list(map(int, input().split()))
    ws.append(w)
    ps.append(v)
  for i in range(len(ws)):  
    for j in range(W - ws[i], -1, -1):
      dpi = dp[j]
      if dpi != -1:
        if dp[j + ws[i]] < dpi + ps[i]:
          dp[j + ws[i]] = dpi + ps[i]
  print((max(dp)))
main()

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

dynamicprogramming()
# Original solution
# -*- coding: utf-8 -*-
"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d

"""
import sys


def solve(N, W, items):
    ans = {0: 0}
    for w, v in items:
        u = dict()
        for x, y in list(ans.items()):
            if x+w <= W and ans.get(x+w, 0) < y+v:
                u[x+w] = y+v
        ans.update(u)
    return max([v for v in list(ans.values())])


def main(args):
    N, W = list(map(int, input().split()))
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


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

# Optimized solution
# -*- coding: utf-8 -*-
"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d

"""
import sys


def solve(N, W, items):
    dp = [0-1] * (W+1)
    dp[0] = 0
    for w, v in items:
        for i in range(W, w-1, -1):
            if dp[i-w] != -1:
                dp[i] = max(dp[i], dp[i-w]+v)
    return max(dp)



def main(args):
    N, W = list(map(int, input().split()))
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
N, W = list(map(int, input().split()))
w, v = [0] * N, [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 j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print((dp[N][W]))
# print(dp)


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

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



# Optimized solution
n, w = list(map(int, input().split()))
w_v = [list(map(int, input().split())) for _ in range(n)]
#import numpy as np
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if j-w_v[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_v[i][0]] + w_v[i][1])

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

def main():
    n, w = list(map(int, input().split()))
    weight = [0 for _ in range(110)]
    value = [0 for _ in range(110)]

    for i in range(n):
        x, y = list(map(int, input().split()))
        weight[i] = x
        value[i] = y

    
    dp = [[0 for _ in range(110000)] for i in range(110)]

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

    print((dp[n][w])) 

main()


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

# Optimized solution
def inpl(): return list(map(int, input().split()))
N, W = inpl()

DP = [0]*(W+1)
for _ in range(N):
    DP2 = [0]*(W+1)
    w, v = inpl()
    for i in range(w):
        DP2[i] = DP[i]
    for i in range(w, W+1):
        DP2[i] = max(DP[i], DP[i-w]+v)
    DP = DP2
print((DP[-1]))
# Original solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N-1)] #0~N-2
#DP[depth:0~N-1][0~W] calc()の結果をメモる
#DP[N-1][]については、W-pwsum>=N-1の重さならN-1の重さ
##W-pwsum<N-1の重さ なら 0
##→W-(N-1)>=pwsumとW-(N-1)<pwsumで場合分け
DP.append([0]*(W+1))
tmppwsum = 0
weiofMinus1, valofNminus1 = wv[N-1]
while W-weiofMinus1>=tmppwsum:
  DP[N-1][tmppwsum] = valofNminus1
  tmppwsum += 1


#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
#    if depth >= N-1:
#      #今の品物が最後なら、以降得られる価値は0
#      DP[depth][pwsum] = 0
#      return 0
#    else:
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れずに次へいく
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = irenai
    return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
#    if depth >= N-1:
#      #今の品物が最後なら、今の品物しか入れられない
#      DP[depth][pwsum] = nowVal
#      return nowVal
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れる入れないの2択
    ireru = nowVal + calc(depth+1, pwsum+nowWei)
    irenai = calc(depth+1, pwsum)
    ans = max(ireru, irenai)
    DP[depth][pwsum] = ans
    return ans
    
print((calc(0, 0)))

# Optimized solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print((max(DP)))
# Original solution
N,Wmax=list(map(int,input().split(' ')))
info=[ list(map(int,input().split(' '))) for i in range(N) ]
W = [ info[i][0] for i in range(N) ]
V = [ info[i][1] for i in range(N) ]

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []

for i in range(N):
	if i==0:
		#重量制限がW[0]以上なら荷物を積むのが最善
		dp.append([ V[0] if W[0]<=w else 0 for w in range(Wmax+1) ])	
	else:
		#今回の重量制限をwとする
		#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
		#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
		#よってこの2つのうち大きいほうをdp[i][w]に採用する
		l = []
		for w in range(Wmax+1):
			val1 = (dp[i-1][w-W[i]]+V[i]) if w-W[i]>=0 else 0
			val2 = dp[i-1][w]
			l.append(max(val1,val2))
		dp.append(l)
print((dp[N-1][Wmax]))

# Optimized solution
N,Wmax=list(map(int,input().split(' ')))
W=[]
V=[]
for _ in range(N):
	w,v = list(map(int,input().split(' ')))
	W.append(w)
	V.append(v)

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print((dp[N-1][Wmax]))
# Original solution
n,k = list(map(int,input().split()))
w=[]
v=[]
dp =[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n):
    a,b = list(map(int,input().split()))
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k+1):
        if sum_w - w[i] >=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

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

# Optimized solution
N, W = list(map(int, input().split()))
a = []
for i in range(N):
    x,y = list(map(int,input().split()))
    a.append([x,y])
dp = [0]*(W+1)
max_weight = 0

for w, v in a:
    max_w = min(max_weight, W-w)
    for old_v, from_i in zip(dp[max_w::-1], list(range(max_w, -1, -1))):
        if dp[from_i+w] < old_v + v:
            dp[from_i+w] = old_v + v
    max_weight = min(max_weight+w, W)

print((max(dp)))
# Original solution
N,W = list(map(int,input().split()))

dp = [0]*(W+1)
L = []
for i in range(N):
    tb,ta = list(map(int,input().split()))
    L.append([ta,tb])

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

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

dp = [0]*(W+1)
L = []
for i in range(N):
    ta,tb = list(map(int,input().split()))
    L.append([tb,ta])

for i in range(N):
    for w in range(W,-1,-1):
        if w-L[i][1]>=0 :dp[w] = max(dp[w],dp[w-L[i][1]]+L[i][0])
print((dp[-1]))
# Original solution
# N, W = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
# #
# N, W, = 6, 15
# ARR = [
#     [6, 5],
#     [5, 6],
#     [6, 4],
#     [6, 6],
#     [3, 5],
#     [7, 2],
# ]



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

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    srr = [[0] * (w+1) for i in range(n+1)]

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            if j - arr[i-1][0] >= 0:
                s1 = srr[i - 1][j]
                s2 = srr[i - 1][j - arr[i-1][0]] + arr[i-1][1]
                srr[i][j] = max(s1, s2)
            else:
                srr[i][j] = srr[i - 1][j]

    print((srr[-1][-1]))

calculate(N, W, ARR)


# Optimized solution
# N, W = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
# #
N, W, = 6, 15
ARR = [
    [6, 5],
    [5, 6],
    [6, 4],
    [6, 6],
    [3, 5],
    [7, 2],
]



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

for i in range(N):
    ARR.append(list(map(int,input().split())))


def calculate(n, w, arr):
    srr = [[0] * (w+1) for i in range(n+1)]

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            if j - arr[i - 1][0] >= 0:
                s1 = srr[i - 1][j]
                s2 = srr[i - 1][j - arr[i - 1][0]] + arr[i - 1][1]
                srr[i][j] = max(s1, s2)
            else:
                srr[i][j] = srr[i-1][j]

    print((srr[-1][-1]))


calculate(N, W, ARR)
# Original solution
n, w = list(map(int, input().split()))
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 for j in range(w+1)]for i in range(n+1)]
for i in range(n+1):
    for j in range(w+1):
        if j-g[i-1][0] < 0:
            m[i][j] = m[i-1][j]
        else:
            m[i][j] = max(m[i-1][j], m[i-1][j-g[i-1][0]]+g[i-1][1])
print((m[n][w]))

# Optimized solution
n, w = list(map(int, input().split()))
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 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-g[i][0] < 0:
            m[i+1][j] = m[i][j]
        else:
            m[i+1][j] = max(m[i][j], m[i][j-g[i][0]]+g[i][1])
print((m[n][w]))
# Original solution
def f(i,w,d):
  if i==n:
    return 0
  if (i,w) not in d:
    if a[i][0]>w:
      d[i,w]=f(i+1,w,d)
    else:
      d[i,w]=max(f(i+1,w,d),f(i+1,w-a[i][0],d)+a[i][1])
  return d[i,w]
n,w=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(n)]
print(f(0,w,{}))

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

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

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

# Optimized solution
n, w = list(map(int, input().split()))
weights, values = list(zip(*[tuple(map(int, input().split()))for _ in range(n)]))
dp = [0]*(w+1)
for i in range(1, n+1):
    for j in reversed(list(range(1, w+1))):
        if j-weights[i-1] < 0:
            continue
        dp[j] = max(dp[j], dp[j-weights[i-1]]+values[i-1])
print((dp[-1]))
# Original solution
N, W = list(map(int, input().split()))
A = []
V = []
for i in range(N):
  a, v = list(map(int, input().split()))
  A.append(a)
  V.append(v)

dp = [[0] * (W+1)]
for i in range(N)[::-1]:
  a = []
  for w in range(W+1):
    if A[i] > w:
      a.append(dp[-1][w])
    else:
      a.append(
        dp[-1][w]
        if dp[-1][w] > dp[-1][w-A[i]] + V[i]
        else dp[-1][w-A[i]] + V[i]
      )
  dp.append(a)

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

# Optimized solution
N, W = list(map(int, input().split()))
A = []
V = []
for i in range(N):
  a, v = list(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]))
# Original solution
def solve(N, W, weight_values):
    dp = [0 for _ in range(W + 1)]
    for i in range(N):
        wi, vi = weight_values[i]
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], vi + dp[w - wi])
    print((dp[W]))

def iln():
    return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
    w_v.append(iln())

solve(N, W, w_v)

# Optimized solution

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

N,W=list(map(int,input().split()))
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0
 
for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print((max(dp)))

# Optimized solution
def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    s = 0
    for w, v in weightValues:
        s += w
        for j in range(min(W, s), w - 1, -1):
            if dp[j - w] + v > dp[j]:
                dp[j] = dp[j - w] + v

    print((max(dp)))


N, W = list(map(int, input().split()))
weightValues = sorted([list(map(int, input().split())) for i in range(N)])
solve(N, W, weightValues)
# Original solution
def solve(N, W, weight_values):
      dp = [0 for _ in range(W + 1)]
     
      for i in range(N):
        wi, vi = weight_values[i]
        for w in range(W, wi - 1, -1): # loop from W down to wi
          if dp[w - wi] + vi > dp[w]:
            dp[w] = dp[w - wi] + vi
     
      print((dp[W]))
    
def iln(): return list(map(int, input().split()))

N, W = iln()
w_v = []
for i in range(N):
	w_v.append(iln())

solve(N, W, w_v)

# Optimized solution
def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    s = 0
    for w, v in weightValues:
        s += w # why ?
        for i in range(min(W, s), w - 1, -1): # why min(W, s)
            if dp[i - w] + v > dp[i]:
                dp[i] = dp[i - w] + v

    print((max(dp)))

def iln(): return list(map(int, input().split()))

N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)
# Original solution
n,max_w = list(map(int,input().split()))
w=[]
v=[]

for i in range(n):
  tmp_w,tmp_v = list(map(int,input().split())) 
  w.append(tmp_w)
  v.append(tmp_v)

dp =[[-1]*(max_w+1) for i in range(n+1)]
  
#i番目以降の品物から、重さの総和がj以下となるように選ぶ
def knapsac(i,j):
  if dp[i][j]>=0:
    return dp[i][j]
  if i == n:
    #品物は残っていない
    dp[i][j] = 0
  elif j < w[i]:
    #品物が入らない
    dp[i][j] = knapsac(i+1,j)
  else:
    #品物が入る→品物を入れる場合と入れない場合を両方試す
    dp[i][j] = max(knapsac(i+1,j),knapsac(i+1,j-w[i])+v[i])
  return dp[i][j]

print((knapsac(0,max_w)))

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

## dp[i][j]:i番目までのアイテムを重さjのナップサックに詰めるときの最大価値
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]))
# Original solution
# coding: utf-8
# Your code here!
N,W=list(map(int,input().split()))

l=[-1]*(W+1)
l[0]=0
dp=l[:]

for i in range(N):
    w,v=list(map(int,input().split()))
    for index,item in enumerate(l):
        if item!=-1 and W>=index+w:
            dp[index+w]=max(item+v,l[index+w])
    l=dp[:]
print((max(l)))


# Optimized solution
# coding: utf-8
# Your code here!
N,W=list(map(int,input().split()))

jwels=[]

for _ in range(N):
    jwels.append(list(map(int,input().split())))

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

for w,v in jwels:
    for i in range(W+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i]+v,dp[i+w])
            
print((max(dp)))
# Original solution
# coding: utf-8
# Your code here!
N,W=list(map(int,input().split()))

jwels=[]

for _ in range(N):
    jwels.append(list(map(int,input().split())))

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

for w,v in jwels:
    for i in range(W+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i]+v,dp[i+w])
            
print((max(dp)))



# Optimized solution
# coding: utf-8
# Your code here!
N,W=list(map(int,input().split()))

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

for _ in range(N):
    w,v=list(map(int,input().split()))
    for i in range(W+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i+w],dp[i]+v)

print((max(dp)))
# Original solution
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

result = []

max_weight = a[1]

def calc(i, queue):
    if len(b) <= i:
        return

    current = b[i]
    prev = queue[-1] if 0 < len(queue) else [0, 0] 
    
    if current[0] + prev[0] <= max_weight:
        result.append(prev[1] + current[1])
    
    next_queue = queue[:]
    next_queue.append([prev[0] + current[0], prev[1] + current[1]])
    calc(i + 1, next_queue)
    calc(i + 1, queue)

calc(0, [])

print((max(result)))

# Optimized solution
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

max_index = a[0]
max_weight = a[1]

dp = [ [0] * (max_weight + 1) for j in range(max_index + 1)]

def solve():
    for i in range(max_index - 1, -1, -1):
        for j in range(max_weight + 1):
            if (j < b[i][0]):
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max([dp[i + 1][j], dp[i + 1][j - b[i][0]] + b[i][1]])
    print((dp[0][max_weight]))

solve()
# Original solution
N,W = [int(v) for v in input().split()]
items = [[int(v) for v in 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):
    w,v = items[i-1]
    for cap in range(W+1):
        if cap - w >= 0:
            dp[i][cap] = max(dp[i][cap],dp[i-1][cap-w]+v)
        dp[i][cap] = max(dp[i][cap],dp[i-1][cap])

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


# Optimized solution
N,W = [int(v) for v in input().split()]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

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

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

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

N,W=list(map(int,input().split()))
opt(N,W)
# Original solution
import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve():
    N, W = list(map(int, input().split()))    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

    #print(dp)
 
    @lru_cache(maxsize=None)
    def dfs(w, i):
        if dp[i][w] >= 0:
            return dp[i][w]
        if i >= N:
            res = 0
        elif w < w_v[i][0]:
            res = dfs(w, i+1)
        else:
            res = max(dfs(w - w_v[i][0], i+1) + w_v[i][1], dfs(w, i+1))

        dp[i][w] = res
        return res

    res = dfs(W, 0)
    print(res)
    
    
if __name__ == "__main__":
    resolve()

# Optimized solution
def resolve():
    N, W = list(map(int, input().split()))    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

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