# Original solution
#####################################################################################################
##### ナップサック問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja
#####################################################################################################


import sys
input = sys.stdin.readline

M, W = list(map(int, input().split()))                                # M: 品物の種類 W: 重量制限

dp_min = 0                                                      # 総和価値の最小値


price_list = [0]
weight_list = [0]

for _ in range(M):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)

# price_list = [0] + list(map(int, input().split()))              # item = 0 は 0 種類の品物を用いた場合に対応するため、参照されることはない。item = 1 で品物の 0 番目に対応させるためにインクリメントが必要となる。
# weight_list = [0] + list(map(int, input().split()))             # item = 0 は 0 種類の品物を用いた場合に対応するため、参照されることはない。item = 1 で品物の 0 番目に対応させるためにインクリメントが必要となる。

# dp[item <= M ][weight <= W]
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                       # 左端と上端の境界条件で W, M を一個ずつ多めに取る

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 重さ 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_max                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          # weight (重量価値) < weight_list[item] (品物の重量) の時は無視してよい
            dp[item][weight] = dp[item - 1][weight]
        else:
            dp[item][weight] = max(dp[item-1][weight], dp[item-1][weight - weight_list[item]] + price_list[item])        # 重複なし: dp[item][weight - weight_list[item]] ⇒　dp[item-1][weight - weight_list[item]]

print((dp[M][W]))

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



M, W = list(map(int, input().split()))                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

dp_min = 0                                                      # 総和価値の最小値

""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る

""" 重さ 0 の時の境界条件 """
for item in range(M+1):
    dp[item][0] = 0                                             # 重さ 0 を実現するのに必要な品物の個数は 0 個

""" 品物 0 個の時の境界条件 """
# for weight in range(W+1):
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          # weight (重量価値) < weight_list[item] (品物の重量) の時は無視してよい
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  # single = True: 重複なし
            if temp > dp[item-1][weight]:                       # max(dp[item-1][weight], temp)
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print((dp[M][W]))