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 = list(range(W, weight_list[item] - 1, -1))

        else:

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

        for weight in S:

            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:

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

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

        for weight in S:

            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:

                dp[weight] = dp[weight - weight_list[item]] + price_list[item]

    return dp[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)

 

print((knapsack_weight(single=True)))

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 = list(range(W, weight_list[item] - 1, -1))
        else:
            S = list(range(weight_list[item], W + 1))
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                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)))

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):
        S = list(range(W, weight_list[item] - 1, -1))
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[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)
print((knapsack_weight(single=True)))

-        if single: -            S = list(range(W, weight_list[item] - 1, -1)) -        else: -            S = list(range(weight_list[item], W + 1)) +        S = list(range(W, weight_list[item] - 1, -1)) +import sys + +input = sys.stdin.readline