CodeEff/ECCO huggingface dataset:
# Original solution
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [[-1] * (target + 1) for _ in range(len(V))]

    def rec(w, index):
        if index == 0 and w >= W[index]:
            return V[index]
        elif index > 0:
            if P[index][w] != -1:
                return P[index][w]
            r = rec(w, index - 1)
            if w >= W[index]:
                y = rec(w - W[index], index - 1) + V[index]
                r = r if r > y else y
            P[index][w] = r
            return r
        return 0

    ret = rec(target, len(V) - 1)
    return ret

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = list(map(int, sys.stdin.read().split()))
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)


# Optimized solution
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [-1] * (target + 1)
    P[target] = 0 # default + max

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if P[i] != -1 and P[i - we] < P[i] + va:
                P[i - we] = P[i] + va

    return max(P)

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = list(map(int, sys.stdin.read().split()))
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)
# Original solution
N,W = list(map(int, input().split()))
dp = [0] * (W + 1)
nupList = [list(map(int, input().split())) for _ in range(N)]

for w, v in nupList:
    for j in range(W, w - 1, -1 ):
        DP = dp[j - w] + v
        if dp[j] < DP:
            dp[j] = DP

print((dp[W]))


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

for w, v in nupList:
    for j in range(W, w - 1, -1 ):
        DP = dp[j - w] + v
        if dp[j] < DP:
            dp[j] = DP

print((dp[W]))

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

    for w, v in nupList:
        for j in range(W, w - 1, -1 ):
            DP = dp[j - w] + v
            if dp[j] < DP:
                dp[j] = DP

    return max(dp)

print((d()))
# 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 iterative_knapsack(wt, val, W, n):
    # Take the equations in recursive_knapsack. Change the recursive call to the table t. CHange all instances of n to i and W to j.
    # Also the table t was initialized using the base conditions of recursive_knapsack.
    t = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, W+1):
            # if weight of item less than knapsack
            if wt[i-1]<=j:
                include = val[i-1] + t[i-1][j-wt[i-1]]       # val[n-1] + recursive_knapsack(wt, val, W-wt[n-1], n-1)
                exclude = t[i-1][j]                          # recursive_knapsack(wt, val, W, n-1)
                t[i][j] = max(include, exclude)
            else:
                t[i][j] = t[i-1][j]                          # recursive_knapsack(wt, val, W, n-1)

    return t[n][W]


print((iterative_knapsack(weights, values, W, n)))

# Optimized solution
def memo_knapsack(w, n):
    if memo[w][n]!=-1:
        return memo[w][n]
    else:
        if w == 0 or n == 0: return 0 # no capacity knapsack has 0 value; no items has 0 value

        if weights[n-1]>w:
            # cant include
            memo[w][n] = memo_knapsack(w, n-1)
            return memo[w][n]

        else:
            include = values[n-1] + memo_knapsack(w - weights[n-1], n-1)
            exclude = memo_knapsack(w, n-1)

            memo[w][n] = max(include, exclude)
            return memo[w][n]

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)

# memo[w][n] - max value we can obtain with capacity w and number of items n
memo = [[-1]*(n+1) for _ in range(W + 1)]

print((memo_knapsack(W, n)))
# Original solution
n,w = list(map(int,input().split()))
dp = {(0,0)}
for i in range(n):
  weight,value = list(map(int,input().split()))
  gone=set()
  for noww,nowv in dp:
    if noww + weight <= w:
      gone.add((noww + weight,nowv + value))
    gone.add((noww,nowv))
  dp = gone
ans = 0
for lastw,lastv in dp:
  ans = max(ans,lastv)
print(ans)

# Optimized solution
n,w = list(map(int,input().split()))
dp = [-1] * (w + 1)
dp[0] = 0
for i in range(n):
  weight,value = list(map(int,input().split()))
  for j in range(w,-1,-1):
    if dp[j] != -1 and weight + j <= w:
      dp[weight+j] = max(dp[weight+j],dp[j] + value)
print((max(dp)))
# Original solution
n,w = list(map(int,input().split()))

lstw, lstv = [], []
for i in range(n):
    w_,v_ = list(map(int,input().split()))
    lstw.append(w_)
    lstv.append(v_)

#dp[i+1][j] := i番目までの商品で重さの総和がj以下の最大価値
dp = [[0 for i in range(w+1)] for _ in range(n+1)]

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

# Optimized solution
n,w = list(map(int,input().split()))

lstw, lstv = [], []
for i in range(n):
    w_,v_ = list(map(int,input().split()))
    lstw.append(w_)
    lstv.append(v_)

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

for i in range(n):
    for j in range(w+1):
        if j < lstw[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-lstw[i]]+lstv[i])
print((dp[n][w]))
# Original solution
def knapsack_1(N, W, lst):
    #N : 品物数
    #W : 重みの総和
    #lst (wi,vi) : 商品iの重みwi、価値vi
    
    #dp[i][j] : i番目の品物から重さの総和がj以下になるように選んだ場合の価値の総和の最大値
    dp = [[0 for i in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for j in range(W+1):
            if j < lst[i][0]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j - lst[i][0]] + lst[i][1])
    return dp[N][W]


n,w = list(map(int,input().split()))
lst = []
for i in range(n):
    w_, v_ =  list(map(int,input().split()))
    lst.append((w_, v_))
print((knapsack_1(n,w,lst)))

# 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):
    wi, vi = wv[i]
    for j in range(w+1):
        if j<wi:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wi]+vi)
            
print((dp[n][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 solve(w,v):
    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 < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print((solve(w,v)))

# Optimized solution
def solve():
  ans = 0
  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(W+1):
      dp[i][j] = max(dp[i-1][j],dp[i][j])
      if j+w<=W:
        dp[i][j+w] = max(dp[i-1][j+w],dp[i-1][j]+v)
  return dp[-1][-1]
print((solve()))
# Original solution
import sys
input = sys.stdin.readline

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

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

npsk_1(N, W)

# Optimized solution
# PyPy3

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

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

npsk_1(N, W)
# Original solution
def aaa():
    N, W = list(map(int, input().split()))
    
    dp = [0] * (W+1) # DP枠_重さ’0’～'W'まで準備
    
    for i in range(N):
        w, v = list(map(int, input().split())) # 商品, 各々重さと価値
        tmp =tuple(dp[:]) # ひとつ前の商品までのDP枠を参照用にコピー
        for j in range(1, W+1): # 各商品のDP枠への落とし込み
            if j  >= w and tmp[j] < tmp[j-w] + v: # 商品の重さよりDP枠の重さが重い場合で...
                dp[j] = tmp[j-w] + v # この商品を加え, 合計価値が up する場合は replace
            else: # 商品の重さよりDP枠の重さが軽い場合と, ↑で価値が up しない場合は...
                dp[j] = tmp[j] # ↑ 参照データをそのままコピー
        
    print((dp[-1]))

aaa()

# Optimized solution
# AC by Pypy not Python
# Pythonで通すためには,  npで配列毎まるっと処理する必要あり

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

dp = [0] * (W+1) # DP枠_重さ’0’～'W'まで準備

for i in range(N):
    w, v = list(map(int, input().split())) # 商品, 各々重さと価値
    tmp = dp[:] # ひとつ前の商品までのDP枠を参照用にコピー
    for j in range(1, W+1): # 各商品のDP枠への落とし込み
        if j  >= w and tmp[j] < tmp[j-w] + v: # 商品の重さよりDP枠の重さが重い場合で...
            dp[j] = tmp[j-w] + v # この商品を加え, 合計価値が up する場合は replace
        else: # 商品の重さよりDP枠の重さが軽い場合と, ↑で価値が up しない場合は...
            dp[j] = tmp[j] # ↑ 参照データをそのままコピー
    
print((dp[-1]))
# Original solution
#!/usr/bin/env python3
N, W=list(map(int, input().split()))
WV=[list(map(int, input().split())) for i in range(N)]
dp = [-1] * (W+1)
dp[0] = 0
for w, v in WV:
    for i in range(W, w-1, -1):
        if dp[i-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print((max(dp)))


# Optimized solution
N, W=list(map(int, input().split()))
WV=[list(map(int, input().split())) for i in range(N)]
dp = [-1] * (W+1)
dp[0] = 0
for w, v in WV:
    for i in range(W, w-1, -1):
        if dp[i-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print((max(dp)))
# Original solution
# -*- coding:utf-8 -*-
"""
問題
https://atcoder.jp/contests/dp/tasks/dp_d

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#d-%E5%95%8F%E9%A1%8C---knapsack-1
"""

def solve():
    N, LIMIT = list(map(int, input().split()))
    W, V = [None], [None]
    for i in range(N):
        w, v = list(map(int, input().split()))
        W.append(w)
        V.append(v)
    
    # dp[i][w] := i個目までの品物を選んだ時の、重さがwのときの価値の最大値
    dp = [[w for w in range(LIMIT+1)] for i in range(N+1)]
    for w in range(LIMIT+1):
        dp[0][w] = 0
    
    #O(N*LIMIT) = O(10**7)
    for i in range(1, N+1):
        for w in range(LIMIT+1):
            if w-W[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
            else:
                dp[i][w] = dp[i-1][w]

    ans = 0
    for w in range(LIMIT+1):
        ans = max(ans, dp[N][w])

    print(ans)


if __name__ == "__main__":
    solve()


# Optimized solution
# -*- coding:utf-8 -*-
"""
問題
https://atcoder.jp/contests/dp/tasks/dp_d

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#d-%E5%95%8F%E9%A1%8C---knapsack-1
"""

def solve():
    """
    Python: TLE (´･_･`)
    """
    N, LIMIT = list(map(int, input().split()))
    W, V = [None], [None]
    for i in range(N):
        w, v = list(map(int, input().split()))
        W.append(w)
        V.append(v)
    
    # dp[i][w] := i個目までの品物を選んだ時の、重さがwのときの価値の最大値
    dp = [[w for w in range(LIMIT+1)] for i in range(N+1)]
    for w in range(LIMIT+1):
        dp[0][w] = 0
    
    #O(N*LIMIT) = O(10**7)
    for i in range(1, N+1):
        for w in range(LIMIT+1):
            if w-W[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
            else:
                dp[i][w] = dp[i-1][w]

    ans = 0
    for w in range(LIMIT+1):
        ans = max(ans, dp[N][w])

    print(ans)


if __name__ == "__main__":
    solve()
# Original solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(N):
    weight = wv[i][0]
    value = wv[i][1]
    for w in range(W+1):
        # 重量に収まる場合のみ価値を加える
        if weight <= w:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print((max(dp[-1])))


# Optimized solution
# ナップザック問題
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(N):
    weight = wv[i][0]
    value = wv[i][1]
    for w in range(W+1):
        # 重量に収まる場合のみ価値を加える
        if weight <= w:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print((max(dp[-1])))
# Original solution
N, W = list(map(int, input().split()))
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

DP = [[0] * M for _ in range(W + 3)]

for i in range(W+1):
    for j, (weight, value) in enumerate(WEIGHTS):
        if i - weight >= 0:
            DP[i+1][j] = max(x if index != j else 0 for index, x in enumerate(DP[max(i - weight + 1, 0)])) + value

print((max(DP[W + 1])))


# Optimized solution
N, W = list(map(int, input().split()))
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

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

for i, (weight, value) in enumerate(WEIGHTS):
    for w in range(W + 1):
        if w - weight >= 0:
            DP[i+1][w] = max(DP[i][w - weight] + value, DP[i][w])
        else:
            DP[i+1][w] = DP[i][w]

print((DP[M][W]))
# Original solution
N, W = list(map(int, input().split()))
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

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

for i, (weight, value) in enumerate(WEIGHTS):
    for w in range(W + 1):
        if w - weight >= 0:
            DP[i+1][w] = max(DP[i][w - weight] + value, DP[i][w])
        else:
            DP[i+1][w] = DP[i][w]

print((DP[M][W]))

# Optimized solution
N, W = list(map(int, input().split()))
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

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

for i, (weight, value) in enumerate(WEIGHTS):
    for w in range(W + 1):
        if w - weight >= 0:
            DP[i+1][w] = max(DP[i][w - weight] + value, DP[i][w])
        else:
            DP[i+1][w] = DP[i][w]

print((DP[M][W]))

# dp_ij := 1~jまでのアイテムからいくつかを選んで総重量iを超えないようにしたときの最大価値

# 0 1 2 3  4  5  6  7  8
# 0 0 0 0  0  0  0  0  0
# 0 0 0 30 30 30 30 30 30
# 0 0 0 30 50 50 50 80 80
# 0 0 0 30 50 60 60 80 90
# Original solution
N, W = list(map(int, input().split()))

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = 0
    flag = 0
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print((dp[W][0]))


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

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = dp[i-1][0]
    flag = dp[i-1][1]
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print((dp[W][0]))
# Original 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)


# print('weight')
# print(weight)
# print('value')
# print(value)


def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# print(dp)
# print(weight)
# print(value)
# max value = dp[何個まで見たか][現在の重さ]
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][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


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




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

def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# max value = dp[何個まで見たか][現在の重さ]
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][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print((dp[N][W]))
# Original solution
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = list(map(int,input().split()))
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = list(map(int,input().split()))
        for i in range(W, w-1, -1):
            if (dp[i] < (dp[i-w] + v)):
                dp[i] = dp[i-w] + v
        #print(dp,sep="\n")

    #4:出力
    print((max(dp)))

if __name__ == '__main__':
    main()

# Optimized solution
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = list(map(int,input().split()))
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = list(map(int,input().split()))
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print((max(dp)))

if __name__ == '__main__':
    main()
# Original solution
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = list(map(int,input().split()))
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = list(map(int,input().split()))
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print((max(dp)))

if __name__ == '__main__':
    main()

# Optimized solution


import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = list(map(int,input().split()))
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [[0]*(W+1) for i in range(N+1)]

    #print(dp)
    #print(dp2)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j: #dpの横が重さだが，jが重さ以下ならそもそも入れられない．
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print((dp[N][W]))

if __name__ == '__main__':
    main()
# Original solution
def knapsack01(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

# Optimized solution

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)