CodeEff/ECCO huggingface dataset:
# Original solution
N,W = list(map(int,input().split()))
w = []
v = []
for i in range(N):
    x,y = list(map(int,input().split()))
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

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

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

# Optimized solution
def MI(): return list(map(int, input().split()))
N,W=MI()
w=[]
v=[]
for i in range(N):
  a,b=MI()
  w.append(a)
  v.append(b)
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  for j in range(W+1):
    if j<w[i]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])      
ans=dp[-1][-1]
print(ans)
# Original solution
def main():
    def solve(N, W, wv):
        dp = [-1] * (W+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            for j in range(W-wi, -1, -1):
                # print('i, wi, j = {}, {}, {}'.format(i, wi, j))
                if dp[j] == -1:
                    continue
                dp[j+wi] = max(dp[j+wi], dp[j] + vi)
                # print(dp)

        return max(dp)

    N, W = list(map(int, input().split()))
    wv = tuple(tuple(map(int, input().split())) for i in range(N))
    print((solve(N, W, wv)))


##########
if __name__ == "__main__":
    main()


# Optimized solution
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=list(map(int,input().split()))
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print((solve(N,W,wv)))
# Original solution
# Educational DP Contest D-knapsack

def knapsack(N, W, wv):
    # initialize
    dp = [list(0 for _ in range(W+1)) for j in range(N+1)]
    
    # DP
    for i in range(N):
        for j in range(W+1):
            if j >= wv[i][0]:
                dp[i+1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
            else:
                dp[i+1][j] = dp[i][j]
    return dp[N][W]

if __name__ == "__main__":
    N, W = list(map(int, input().split()))
    wv = []
    for _ in range(N):
        wv.append(list(map(int, input().split())))
    print((knapsack(N, W, wv)))

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

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

for i in range(N):
    for j in range(W+1):
        if j >= wv[i][0]:
            dp[i+1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print((dp[N][W]))
# Original solution
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

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

#N(i+1)個目の品物を追加したときにWjとなる場合のWj地点の最大価値
dp = [0 for _ in range(W+1)]

for i in range(N) :
  dptemp = copy.deepcopy(dp)
  for j in range(W+1) :
    if dptemp[j] > 0 and j+H[i][0] <= W:
      dp[j+H[i][0]] = max(dptemp[j+H[i][0]], dptemp[j] + H[i][1])
    
  dp[H[i][0]] = max(dptemp[H[i][0]], H[i][1])
  #print (dp)      
#print (dp)

print((max(dp)))

# Optimized solution
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

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

#N(i+1)個目の品物を追加したときにWjとなる場合のWj地点の最大価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1, N+1) :
  for j in range(W+1) :
    dp[i][j] = max(dp[i-1][j], dp[i][j])
    if dp[i-1][j] > 0 and j+H[i-1][0] <= W:
      dp[i][j+H[i-1][0]] = max(dp[i-1][j+H[i-1][0]], dp[i-1][j] + H[i-1][1])
    
  dp[i][H[i-1][0]] = max(dp[i-1][H[i-1][0]], H[i-1][1])
  #print (dp[i])      
#print (dp)

print((max(dp[N])))
# Original solution
N, Weight = list(map(int, input().split()))
w = []
V = []
for _ in range(N):
    w_tmp, v = list(map(int, input().split()))
    w.append(w_tmp)
    V.append(v)

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

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

print((dp[N][Weight]))

# Optimized solution
N, W = list(map(int, input().split()))
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = list(map(int, input().split()))
    weight.append(w_tmp)
    value.append(v_tmp)

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

print((dp[N][W]))
# Original solution
def solve():
    dp = {}
    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]:
                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 = list(map(int, input().split()))
w = {}
v = {}
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))
print((solve()))

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

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

# Optimized solution
n,w=list(map(int,input().split()))
mer=[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 j in range(w+1):
        if j>=mer[i-1][0]:
            dp[i][j]=mer[i-1][1]+dp[i-1][j-mer[i-1][0]]
        dp[i][j]=max(dp[i][j],dp[i-1][j])
print((dp[-1][-1]))
# Original solution
import sys 
sys.setrecursionlimit(2147483647)

N,W = list(map(int,input().split()))
A = [list(map(int, input().split())) for i in range(N)]

def dfs(i,w):
    if (i,w) in dic: return dic[(i,w)]
    if i == N or w <=0: 
        dic[(i,w)] = 0
        return 0
    ma = 0 
    res1 = res2 = 0 
    if A[i][0] <=w:
        res1 = dfs(i + 1,w - A[i][0]) + A[i][1]
    res2 = dfs(i + 1,w)
    ma = max(res1,res2)
    dic[(i,w)] = ma
    return ma
dic = {}
res = dfs(0,W)
print(res)

# Optimized solution
import sys 
sys.setrecursionlimit(2147483647)

N,W = list(map(int,input().split()))
A = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for _ in range(W+1) ] for _ in range(N + 1)] 

for i in range(1,N + 1): 
    for j in range(W + 1): 
        if j - A[i-1][0] >= 0:
            res1 = dp[i - 1][j - A[i-1][0]] + A[i - 1][1]
            res2 = dp[i - 1][j]
            dp[i][j] = max(res1,res2)
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
print((max(dp[N])))
# Original solution
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				# w_v_list[i][1] = 0
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		dp[(i+1)%3] = [0]*(w+1)
		# for i in dp:print(*i)
		# print("\n")
	print((dp[(n-1)%3][w]))




if __name__ == "__main__":
	solve()

# Optimized solution
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				# w_v_list[i][1] = 0
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
		# for i in dp:print(*i)
		# print("\n")
	print((dp[(n-1)%3][w]))




if __name__ == "__main__":
	solve()
# Original solution
n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(list(range(w + 1))):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print((a[-1]))


# Optimized solution
n, w = [int(i) for i in input().split()]
dp = [0] * (w + 1)
for _ in range(n):
    u, v = [int(i) for i in input().split()]
    for i in reversed(list(range(w - u + 1))):
        dp[i + u] = max(dp[i + u], dp[i] + v)

print((max(dp)))
# Original solution
def knapsack(N,W,weight,value):
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1): 
        dp[0][i]=0
    #DP
    for i in range(N):
        for w in range(W+1):
            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]

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

print((knapsack(n,w,weight,value)))

# Optimized solution
n,w=list(map(int,input().split()))
weight=[]
value=[]
for i in range(n):
    x,v=list(map(int,input().split()))
    weight.append(x)
    value.append(v)
    
dp=[[0 for i in range(w+1)]for i in range(n+1)]

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

print((dp[-1][-1]))
# Original solution
N, W = list(map(int, input().split()))

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

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

for i in range(N):
    wi, vi = wv[i]

    for j in range(wi):
        dp[i+1][j] = dp[i][j]

    for j in range(wi, W+1):
        dp[i+1][j] = max(dp[i][j], dp[i][j-wi] + vi)

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


# Optimized solution
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(eval(input()))

N, W = geta(int)
cur = [0] * (W+1) 

for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w,W+1):
        tmp = cur[j-w] + v
        if tmp > cur[j]: update[j] = tmp
    
    cur = update

print((cur[W]))
# Original solution
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: list(map(fn, readline().split()))
gete = lambda fn: fn(readline())


N, W = geta(int)
cur = [0] * (W+1) 

for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w,W+1):
        tmp = cur[j-w] + v
        if tmp > cur[j]: update[j] = tmp
    
    cur = update

print((cur[W]))


# Optimized solution
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: list(map(fn, readline().split()))
gete = lambda fn: fn(readline())

def main():
    N, W = geta(int)
    cur = [0] * (W+1) 

    for i in range(N):
        w, v = geta(int)
        update = cur[:]
        for j in range(w,W+1):
            tmp = cur[j-w] + v
            if tmp > cur[j]: update[j] = tmp
        
        cur = update

    print((cur[W]))

if __name__ == "__main__":
    main()
# Original solution
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N+1)] #1_indexed
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for dw,dv in list(dp[i-1].items()):
        dp[i][dw] = max(dp[i][dw],dv)
        if dw+w<=W:
            dp[i][dw+w] = max(dp[i][dw+w],dv+v)
print((max(dp[-1].values())))


# Optimized solution
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(list(range(1,N+1)),list(range(W+1))):
    w,v = wv[i-1]
    if j-w>=0:
        dp[i][j] = max(dp[i][j],dp[i-1][j-w]+v)
    dp[i][j] = max(dp[i][j],dp[i-1][j])
print((dp[-1][-1]))
# Original solution
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(list(range(1,N+1)),list(range(W+1))):
    w,v = wv[i-1]
    if j-w>=0:
        dp[i][j] = max(dp[i][j],dp[i-1][j-w]+v)
    dp[i][j] = max(dp[i][j],dp[i-1][j])
print((dp[-1][-1]))


# Optimized solution
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(W+1):
        if j-w>=0:
            dp[i][j] = max(dp[i][j],dp[i-1][j-w]+v)
        dp[i][j] = max(dp[i][j],dp[i-1][j])
print((dp[-1][-1]))
# Original solution
n,w=list(map(int, input().split()))
wv=[list(map(int, input().split())) for _ in range(n)]

dp = [[-float("inf") for _ in range(w+1)] for _ in range(n+1)]
dp[0][0] = 0

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

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

print((dp[-1][-1]))
# Original solution
N, W = list(map(int, input().split()))
weights, values = [], []
for _ in range(N):
    w, v = list(map(int, input().split()))
    weights.append(w)
    values.append(v)

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        #print(cw, cv, i)
        if i == -1:
            return cv
        
        # take
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            # dont take
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)


print((solve(N, W, weights, values)))

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

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        #print(cw, cv, i)
        if i == -1:
            return cv
        
        # take
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            # dont take
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)

def solve_fast(n_items, max_w, weights, values):
    dp =  [[0]*(max_w+1) for _ in range(n_items)]
    dp[0] = [values[0] if i >= weights[0] else 0 for i in range(max_w+1)]

    for r in range(1, n_items):
        cw, cv = weights[r], values[r]
        for c in range(max_w+1):
            if cw > c:
                dp[r][c] = dp[r-1][c]
            else:
                dp[r][c] = max(dp[r-1][c], dp[r-1][c-cw] + cv)

    #for r in dp:
        #print(r)

    return dp[-1][-1]


print((solve_fast(N, W, weights, values)))
# Original solution
n,w=list(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]=list(map(int,input().split()))
for i in range(1,w+1):
	for j in range(1,n+1):
		if i-wt[j-1]>=0:
			# print(i,j)
			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]))
# for i in range(w+1):
# 	print(dp[i])


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


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


# Optimized 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)]


for i in range(n):
    for j in range(w+1):
        if i==0:
            if j>=wv[i][0]:
                dp[i][j]=wv[i][1]
        else:
            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[n-1][w]))
# Original solution
N,W=list(map(int,input().split()))
weights,profits = [0]*N, [0]*N
def solve_knapsack(profits, weights, capacity):
    # basic checks
    n = len(profits)
 
    dp = [[0 for x in range(capacity+1)] for y in range(n)]
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    for i in range(0, n):
        dp[i][0] = 0
    for c in range(0, capacity+1):
        if weights[0] <= c: dp[0][c] = profits[0]
    for i in range(1, n):
        for c in range(1, capacity+1):
            if weights[i] <= c:
                dp[i][c] = max(profits[i] + dp[i - 1][c - weights[i]], dp[i - 1][c])
            else: dp[i][c]  = dp[i - 1][c]
 
    # maximum profit will be at the bottom-right corner.
    return dp[n - 1][capacity]
  
def main():
 
    for i in range(N):
        weights[i],profits[i] = list(map(int,input().split()))
    res = solve_knapsack(profits, weights, W)
 
    print(res)
if __name__ == "__main__":
	main()

# Optimized solution
def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print((max(t)))
main()
# Original solution
import sys
input=sys.stdin.readline


N,W=list(map(int,input().split()))
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = list(map(int,input().split()))
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

# Optimized solution
import sys
input=sys.stdin.readline


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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = list(map(int,input().split()))
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()
# Original solution
N,W=list(map(int,input().split()))

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = list(map(int,input().split()))
        for c in range(capacity, weights-1, -1):
            dp[c] = max(dp[c], profits + dp[c - weights])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = list(map(int,input().split()))
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()
# Original solution
import sys
input=sys.stdin.readline
 
n,w=list(map(int,input().split()))
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=list(map(int,input().split()))
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return dp[-1]
print((ans(n,w)))

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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = list(map(int,input().split()))
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()