import sys

input = sys.stdin.readline





def max2(x, y):

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

    if x > y:

        return x

    else:

        return y





def knapsack_weight(single=True):

    """

    重さが小さい時のナップサックDP

    :param single: True = 重複なし

    """

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

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

    dp = [dp_min] * (W + 1)



    for item in range(N):

        if single:

            S = reversed(list(range(weight_list[item], W + 1)))

        else:

            S = list(range(weight_list[item], W + 1))

        for weight in S:

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

    return dp[W]



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





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)



print((knapsack_weight(single=True)))



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



import sys

input = sys.stdin.readline





def max2(x, y):

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

    if x > y:

        return x

    else:

        return y





def knapsack_weight(single=True):

    """

    重さが小さい時のナップサックDP

    :param single: True = 重複なし

    """

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



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

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

    dp = [dp_min] * (W + 1)



    for _ in range(N):

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

        if single:

            S = reversed(list(range(w, W + 1)))

        else:

            S = list(range(w, W + 1))

        for weight in S:

            dp[weight] = max2(dp[weight], dp[weight - w] + price)

    return dp[W]



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





print((knapsack_weight(single=True)))

import sys

input = sys.stdin.readline


def max2(x, y):
    """pythonの組み込み関数 max は2変数に対しては遅い！！"""
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)
    for item in range(N):
        if single:
            S = reversed(list(range(weight_list[item], W + 1)))
        else:
            S = list(range(weight_list[item], W + 1))
        for weight in S:
            dp[weight] = max2(
                dp[weight], dp[weight - weight_list[item]] + price_list[item]
            )
    return dp[W]


#######################################################################################################
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)
print((knapsack_weight(single=True)))
################################################################################################################################################

import sys

input = sys.stdin.readline


def max2(x, y):
    """pythonの組み込み関数 max は2変数に対しては遅い！！"""
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    N, W = list(map(int, input().split()))  # N: 品物の種類 W: 重量制限
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)
    for _ in range(N):
        w, price = list(map(int, input().split()))
        if single:
            S = reversed(list(range(w, W + 1)))
        else:
            S = list(range(w, W + 1))
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - w] + price)
    return dp[W]


#######################################################################################################
print((knapsack_weight(single=True)))

+    N, W = list(map(int, input().split()))  # N: 品物の種類 W: 重量制限 -    for item in range(N): +    for _ in range(N): +        w, price = list(map(int, input().split())) -            S = reversed(list(range(weight_list[item], W + 1))) +            S = reversed(list(range(w, W + 1))) -            S = list(range(weight_list[item], W + 1)) +            S = list(range(w, W + 1)) -            dp[weight] = max2( -                dp[weight], dp[weight - weight_list[item]] + price_list[item] -            ) +            dp[weight] = max2(dp[weight], dp[weight - w] + price) -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) -################################################################################################################################################