CodeEff/ECCO huggingface dataset:
# Original solution
n, w = list(map(int, input().split()))
wv = []
for i in range(n):
    wv_ = list(map(int, input().split()))
    wv.append(wv_)
dp = [0]*(w+1)
for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp_ = dp[j - wv[i][0]] + wv[i][1]
        if dp[j] < dp_:
            dp[j] = dp_
print((max(dp)))

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

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

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

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

print((max(dp[N])))

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

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

for i in range(N):
  w,v = list(map(int,input().split()))
  for j in range(len(dp[i]) - 2, -1, -1):
    if dp[i][j] == -1:
      continue
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    if j + w >= len(dp[i]):
      continue
    dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)

print((max(dp[N])))
# Original solution
import sys
input = sys.stdin.readline
def main():
	N,W = list(map(int, input().split()))
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = list(map(int, input().split()))
		for i in range(W,0,-1):
			if i>=w:
				dp[i] = max(dp[i],dp[i-w]+v)
		
	print((dp[-1]))

if __name__ == '__main__':
	main()

# Optimized solution
import sys
input = sys.stdin.readline
def main():
	N,W = list(map(int, input().split()))
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = list(map(int, input().split()))
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print((dp[-1]))

if __name__ == '__main__':
	main()
# Original solution
N,W=list(map(int,input().split()))
v=[]
w=[]
for _ in range(N):
    ww,vv=list(map(int,input().split()))
    v.append(vv)
    w.append(ww)

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

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

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

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

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

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

for i in range(1,N):
    for j in range(W):
        if j+1>w[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j]=dp[i-1][j]
print((dp[-1][-1]))
# Original solution
x,y=list(map(int,input().split()))
yo=[]
yo0=[]
for __ in range(x):
    a,b=list(map(int,input().split()))
    yo.append(a)
    yo0.append(b)
lol=[]
for i in range(x+1):
    lol.append([0]*(y+1))
for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            lol[i][j]=lol[i-1][j]
        else:
            lol[i][j]=max(lol[i-1][j],yo0[i-1]+lol[i-1][j-yo[i-1]])
print((lol[x][y]))            

# Optimized solution
x,y=list(map(int,input().split()))
yo=[]
yo0=[]
for __ in range(x):
    a,b=list(map(int,input().split()))
    yo.append(a)
    yo0.append(b)
lol=[0]*(y+1)
lol0=[0]*(y+1)
k=[0]*(y+1)
#print(lol,lol0)
for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            #print(j,lol0[j],lol[j])
            lol0[j]=lol[j]
        else:
            lol0[j]=max(lol[j],yo0[i-1]+lol[j-yo[i-1]])
    lol=lol0[:]
    lol0=k[:]
print((lol[y]))
# Original solution
import copy
N, W = list(map(int, input().split()))

WV = [list(map(int,input().split())) for _ in range(N) ]


costs = [(0,0)]

for w, v in WV:
    new_costs = copy.deepcopy(costs)
    for cw, cv in costs:
        if cw + w > W:
            continue
        new_costs.append((cw + w, cv + v))
    costs = new_costs



print(( max(costs,key=lambda item:item[1])[1]))



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

WV = [list(map(int,input().split())) for _ in range(N) ]


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(list(range(W + 1))):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print((max(costs)))
# Original solution
N,W=list(map(int,input().split()))
li=[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(1,W+1):
        if j < li[i-1][0]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-li[i-1][0]]+li[i-1][1])
print((dp[N][W]))


# Optimized solution
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    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 weight in range(W+1):
            dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight])
            if weight>=w[i]:
                dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight-w[i]]+v[i])
    print((dp[N][W]))

if __name__ == '__main__':
    main()
# Original solution
#d
n,W=list(map(int,input().split()))
w=[0]
v=[0]
for i in range(n):
    x,y=list(map(int,input().split()))
    w.append(x)
    v.append(y)

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

for i in range(1,n+1):
    for j in range(W+1):
        dp[i][j]=dp[i-1][j]#if文Falseのときの値に困らないように
        if j-w[i]>=0:
            dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
print((dp[n][W]))


# Optimized 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)))
# Original solution
#メモ化したもの(修正版)
n,w=list(map(int,input().split()))
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
   dp.append([])
   for l in range(w+1):
       dp[k].append(-1)
def rec(i,j):
   if dp[i][j]>=0:
       return dp[i][j]
   if i==n:
       res=0
   elif j<a[i][0]:
       res=rec(i+1,j)
   else:
       res=max(rec(i+1,j),rec(i+1,j-a[i][0])+a[i][1])
   dp[i][j]=res
   return res
print((rec(0,w)))

# Optimized solution
n,w=list(map(int,input().split()))
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
for i in range(n):
   for j in range(w+1):
       if j<a[i][0]:
           dp[i+1][j]=dp[i][j]
       else:
           dp[i+1][j]=max(dp[i][j],dp[i][j-a[i][0]]+a[i][1])
print((dp[n][w]))
# Original solution
from sys import stdin
from functools import lru_cache
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]


@lru_cache(None)
def dp(w: 'int', n: 'int') -> 'int':
    if w == 0 or n == 0:
        return 0
    if s[n - 1][0] > w:
        return dp(w, n - 1)
    else:
        return max(dp(w, n - 1), dp(w - s[n - 1][0], n - 1) + s[n - 1][1])


print((dp(W, N)))


# Optimized solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

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

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

print((dp[N][W]))
# Original solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

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

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

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


# Optimized solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w],
                             dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print((dp[W]))
# Original solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w],
                             dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print((dp[W]))


# Optimized solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print((dp[W]))
# Original solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print((dp[W]))


# Optimized solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)

for n in range(1, N + 1):
    w0, v0 = s[n - 1]
    for w in range(W, w0 - 1, -1):

        dp[w] = max(dp[w], dp[w - w0] + v0)

print((dp[W]))
# Original solution
# using dp with memoization, TLE
from sys import stdin
N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)

for n in range(1, N + 1):
    w0, v0 = s[n - 1]
    for w in range(W, w0 - 1, -1):

        dp[w] = max(dp[w], dp[w - w0] + v0)

print((dp[W]))


# Optimized solution
from sys import stdin

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

wv = (list(map(int, input().split())) for _ in range(N))

dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        dp[j] = max(dp[j], DP)

print((max(dp)))


# Optimized solution
def dp():
    n, W = list(map(int, input().split()))
    wv = (list(map(int, input().split())) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in wv:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print((dp()))
# Original solution
# atcoder DPまとめ
# D_Knapsack1

# def get_inputs():
#     [n, w] = [int(x) for x in input().split()]
#     g = []
#     for _ in range(n):
#         g.append([int(x) for x in input().split()])
#
#     return n, w, g


if __name__ == "__main__":
    
    n, w = list(map(int, input().split()))
    
    #### First Try
    # この方法では後半の問題でTLEになってしまう
    # 二重ループの部分で時間がかかっている
    # # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    # dp = [[0] * (w + 1) for _ in range(n + 1)]
    #
    # for i in range(1, n + 1):
    #     for wgt in range(w + 1):
    #         if wgt >= g[i -1][0]:
    #             dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
    #         else:
    #             dp[i][wgt] = dp[i - 1][wgt]
    #
    # print(max(dp[n]))

    ### Second Try
    # 動的計画法の部分で、古いiの情報は不要で一つ前の状態さえあれば解ける
    # そこに着目し、かつ不要な判定や更新を減らすために、あるiの時に、
    # 大きなwから最適値を求めるようにする

    # dp[w]は,現在評価中のiにおいて、重さwの時の最大価値の値


    ### Third Try
    # maxをやめてif文に変更

    ### Fourth Try
    # 最初に荷物の情報をリストに読み込んでいたが、そこが時間がかかているようなので逐次読み込みに修正

    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = list(map(int, input().split()))
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp

    print((dp[w]))


# Optimized solution
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = list(map(int, input().split()))
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = list(map(int, input().split()))
print((calc(num,capacity)))
# Original solution
def knapsack(weight,value,N,W,i,cache):
    if i == N or W <= 0:
        return 0
    if cache[i][W] != 0:
        return cache[i][W]
    op1,op2 = 0,0
    if weight[i] <= W:
        op1 = value[i] + knapsack(weight,value,N,W-weight[i],i+1,cache)
    op2 = knapsack(weight,value,N,W,i+1,cache)
    cache[i][W] = max(op1,op2)
    return cache[i][W]

N,W = list(map(int,input().split()))
weight = []
value = []
for i in range(N):
    w,v = list(map(int,input().split()))
    weight.append(w)
    value.append(v)
cache = [[0 for i in range(W+1)] for j in range(N+1)]
print((knapsack(weight,value,N,W,0,cache)))

# Optimized solution
N,W = list(map(int,input().split()))
weight = []
value = []
for i in range(N):
    w,v = list(map(int,input().split()))
    weight.append(w)
    value.append(v)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        op1,op2 = 0,0
        if weight[i-1] <= j:
            op1 = value[i-1] + dp[i-1][j-weight[i-1]]
        op2 = dp[i-1][j]
        dp[i][j] = max(op1,op2)
print((dp[N][W]))
# Original solution
def solve():
    max_weight, list_of_weight_and_value = read()
    result = think(max_weight, list_of_weight_and_value)
    write(result)


def read():
    n, max_weight = read_int(2)
    list_of_weight_and_value = []
    for i in range(n):
        list_of_weight_and_value.append(read_int(2))
    return max_weight, list_of_weight_and_value


def read_int(n):
    return list([int(x) for x in read_line().split(' ')])[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(max_weight, list_of_weight_and_value):
    MAX_WEIGHT = 10 ** 5
    MAX_N = 100
    INVALID_VALUE = MAX_WEIGHT * MAX_N + 1

    # dp[w] means max value at total weight 'w'
    dp = [INVALID_VALUE for x in range(max_weight + len(list_of_weight_and_value) + 1)]
    dp[0] = 0

    for weight, value in list_of_weight_and_value:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] != INVALID_VALUE and i + weight < len(dp):
                if dp[i + weight] == INVALID_VALUE:
                    dp[i + weight] = dp[i] + value
                else:
                    dp[i + weight] = max(dp[i + weight], dp[i] + value)
    return max([x for x in dp[:max_weight + 1] if x != INVALID_VALUE])


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

# Optimized solution
def solve():
    max_weight, list_of_weight_and_value = read()
    result = think(max_weight, list_of_weight_and_value)
    write(result)


def read():
    n, max_weight = read_int(2)
    list_of_weight_and_value = []
    for i in range(n):
        list_of_weight_and_value.append(read_int(2))
    return max_weight, list_of_weight_and_value


def read_int(n):
    return list([int(x) for x in read_line().split(' ')])[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(max_weight, list_of_weight_and_value):
    MAX_WEIGHT = 10 ** 5
    MAX_N = 100
    INVALID_VALUE = -1

    # dp[w] means max value at total weight 'w'
    dp = [INVALID_VALUE for x in range(max_weight + len(list_of_weight_and_value) + 1)]
    dp[0] = 0

    for weight, value in list_of_weight_and_value:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] != INVALID_VALUE and i + weight < len(dp):
                if dp[i + weight] == INVALID_VALUE:
                    dp[i + weight] = dp[i] + value
                else:
                    dp[i + weight] = max(dp[i + weight], dp[i] + value)
    return max([x for x in dp[:max_weight + 1] if x != INVALID_VALUE])


def write(result):
    print(result)


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

dp=[[0]*(w+1) for _ in range(n+1)]
#dpテーブル

def rec(i,j):#再帰　i:何個目の商品を見てるか　j:残りのナップサックの容量
    if dp[i][j] != 0:#メモされてればそれを返す
        return dp[i][j]
    res = 0
    if i == n:#すべての商品を調べ終えた
        return res
    else:
        if j - l[i][0] < 0:#容量が足りない
            ans = rec(i+1,j)
        else:
            #品物を入れるときと入れないとき両方調べる
            ans = max(rec(i+1,j),rec(i+1,j-l[i][0]) + l[i][1])
    dp[i][j] = ans#メモして返す
    return dp[i][j]

print((rec(0,w)))

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

dp=[[0]*(w+1) for _ in range(n+1)]
#dp:=i番目以降の商品から重さの総和がj以下となるように選んだ時の価値の総和の最大

#初期条件 dpｗｐ0で作ってるのでいらない
for j in range(w):dp[n][j] = 0

#漸化式
#dp[i][j] = dp[i+1][j] (j < w[i])
#           max(dp[i+1][j] , dp[i+1][j-w[i]]+v[i]) (otherwise)
for i in reversed(list(range(n))):
    for  j in range(w+1):
        if j < l[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j] , dp[i+1][j - l[i][0]] + l[i][1] )

print((dp[0][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)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える

for i in range(N):
    for j in range(W+1):#重さ0からWまでチェック
        if j-w[i]>=0:#入れてもOKな場合,容量と価値を足す
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:#何も入れずに先に進む
            dp[i+1][j]=dp[i][j]
print((max(dp[N])))


# 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 + 2) for i in range(N + 2)]
"""
DP[0][W]
DP[i][j]
i:荷物の個数
j:残り容量
"""
for i in range(N):
    for j in range(W+1):
        if j>=w[i]:#残り容量に余裕があるとき
            DP[i+1][j]=max(DP[i][j],DP[i][j-w[i]]+v[i])
        else:
            DP[i+1][j]=DP[i][j]

print((max(DP[N])))
# Original solution
N,W = [int(i) for i in input().split()]
w = [] # limit weight to knapsack capacity
v = [] # maximize value
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
mem = [[0]*(W+1) for i in range(N)]
for i in range(w[0], W+1):
  mem[0][i] = v[0]
for i in range(1, N):
  for j in range(1, W+1):
    if w[i] > j:
      mem[i][j] = mem[i-1][j]
    else:
      mem[i][j] = max(mem[i-1][j], v[i] + mem[i-1][j - w[i]])
#print(mem)
print(("%s" % mem[N-1][W]))

# Optimized solution
N,W = [int(i) for i in input().split()]
dp = [0 for i in range(W+1)] # dp[i] is the the max value you have achieve with weight i
for i in range(N):
  w,value = [int(i) for i in input().split()]
  for weight in range(W-w, -1, -1): # range of kanpsack weight in which i can push the current item
    dp[weight + w] = max(dp[weight + w], dp[weight] + value)
print(("%s" % dp[W]))
# Original solution
def p_d():
    N, W = list(map(int, input().split()))
    dp = [[0] * (W + 1) for _ in range(N + 1)]

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

    print((max(dp[N])))


if __name__ == '__main__':
    p_d()


# Optimized solution
def p_d():
    N, W = list(map(int, input().split()))
    dp = [[0] * (W + 1) for _ in range(N + 1)]

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

    print((max(dp[N])))


if __name__ == '__main__':
    p_d()
# Original solution
def p_d():
    N, W = list(map(int, input().split()))
    dp = [[0] * (W + 1) for _ in range(N + 1)]

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

    print((max(dp[N])))


if __name__ == '__main__':
    p_d()


# Optimized solution
def p_e():
    """
    ナップサック問題（制約厳しい版） 
    """
    N, W = list(map(int, input().split()))
    dp = [0] * (W + 1)
    for i in range(1, N + 1):
        w, v = list(map(int, input().split()))
        NEXT = [0] * (W + 1)
        for j in range(1, W + 1):
            if j - w >= 0:
                NEXT[j] = max(v + dp[j - w], dp[j])
            else:
                NEXT[j] = dp[j]
        dp = NEXT

    print((max(NEXT)))


if __name__ == '__main__':
    p_e()
# Original solution
import sys

input = sys.stdin.readline


N, W = list(map(int, input().split()))
#x = [tuple(map(int, input().split())) for _ in range(N)]

x = [None] * N
for i in range(N):
    x[i] = tuple(map(int, input().split()))
    
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i, (w, v) in enumerate(x, 1):
    dpi = dp[i]
    dpim = dp[i-1]    
    for j in range(1, W + 1):
        if w <= j:
            a = dpim[j - w] + v
            if a > dpim[j]:
                dpi[j] = a
            else:
                dpi[j] = dpim[j]
        else:
            dpi[j] = dpim[j]

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

# Optimized solution
#!/usr/bin/env python3

#import
#import math
#import numpy as np
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (W + 1)

for w, v in wv:
    for i in range(W, 0, -1):
        if i - w < 0:
            break

        dp[i] = max(dp[i], dp[i - w] + v)
            
print((dp[W]))