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

input = sys.stdin.readline







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



price_list = []

weight_list = []

for _ in range(N):

    weight, price = list(map(int, input().split()))

    price_list.append(price)

    weight_list.append(weight)





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



def max2(x,y):

    """ pythonの組み込み関数 max は２変数に対しては遅い！！ """

    if x>y:

        return x

    else:

        return y





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



""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """

dp = [dp_min] * (W + 1)



for item in range(N):

    for weight in reversed(list(range(weight_list[item], W + 1))):

        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])





print((dp[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]))

import sys

input = sys.stdin.readline
N, W = list(map(int, input().split()))  # N: 品物の種類 W: 重量制限
price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)
################################################################################################################################################
def max2(x, y):
    """pythonの組み込み関数 max は２変数に対しては遅い！！"""
    if x > y:
        return x
    else:
        return y


dp_min = 0  # 総和価値の最小値
""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [dp_min] * (W + 1)
for item in range(N):
    for weight in reversed(list(range(weight_list[item], W + 1))):
        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
print((dp[W]))

-M, W = list(map(int, input().split()))  # M: 品物の種類 W: 重量制限 -single = True  # True = 重複なし -price_list = [0] -weight_list = [0] -for _ in range(M): +N, W = list(map(int, input().split()))  # N: 品物の種類 W: 重量制限 +price_list = [] +weight_list = [] +for _ in range(N): +def max2(x, y): +    """pythonの組み込み関数 max は２変数に対しては遅い！！""" +    if x > y: +        return x +    else: +        return y + + -""" 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])) +""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """ +dp = [dp_min] * (W + 1) +for item in range(N): +    for weight in reversed(list(range(weight_list[item], W + 1))): +        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item]) +print((dp[W]))