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

##### ナップサック問題 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]))
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]))
#####################################################################################################
##### ナップサック問題 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]))

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

-##################################################################################################### -##### ナップサック問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja -##################################################################################################### -dp_min = 0  # 総和価値の最小値 +single = True  # True = 重複なし -# 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_min = 0  # 総和価値の最小値 +""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """ -for item in range(M + 1):  # 左端の境界条件 +""" 重さ 0 の時の境界条件 """ +for item in range(M + 1): -# for weight in range(W+1):                                     # 上端の境界条件 -#     dp[0][weight] = dp_max                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い） +""" 品物 0 個の時の境界条件 """ +# for weight in range(W+1): +#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い） -            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]] +            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]