def d_simple_knapsack(N, W, Baggage):

    from collections import defaultdict

    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値

    dp = defaultdict(int)

    dp[0] = 0  # 重さ0で達成できる価値は0とする

    for w, v in Baggage:

        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、

        # 注目した荷物を入れても重さがWを超えなければ、

        # ナップサックに荷物を入れて価値の最大値を更新する

        tmp = defaultdict(int)  # 価値の最大値を更新できた荷物の重さの情報

        for kw, kv in list(dp.items()):

            if kw + w <= W:

                if kw + w in dp:

                    tmp[kw + w] = max(dp[kw + w], kv + v)

                else:

                    tmp[kw + w] = kv + v

        for key, value in list(tmp.items()):

            dp[key] = value

    ans = max(dp.values())

    return ans



N, W = [int(i) for i in input().split()]

Baggage = [[int(i) for i in input().split()] for j in range(N)]

print((d_simple_knapsack(N, W, Baggage)))
def d_simple_knapsack(N, W, Baggage):

    from collections import defaultdict

    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値

    dp = defaultdict(int)

    dp[0] = 0  # 重さ0で達成できる価値は0とする

    for w, v in Baggage:

        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、

        # 注目した荷物を入れても重さがWを超えなければ、

        # ナップサックに荷物を入れて価値の最大値を更新する

        latest_dp = list(dp.items())

        for kw, kv in latest_dp:

            if kw + w <= W:

                dp[kw + w] = max(dp[kw + w], kv + v)

    ans = max(dp.values())

    return ans



N, W = [int(i) for i in input().split()]

Baggage = [[int(i) for i in input().split()] for j in range(N)]

print((d_simple_knapsack(N, W, Baggage)))
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict

    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        tmp = defaultdict(int)  # 価値の最大値を更新できた荷物の重さの情報
        for kw, kv in list(dp.items()):
            if kw + w <= W:
                if kw + w in dp:
                    tmp[kw + w] = max(dp[kw + w], kv + v)
                else:
                    tmp[kw + w] = kv + v
        for key, value in list(tmp.items()):
            dp[key] = value
    ans = max(dp.values())
    return ans


N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print((d_simple_knapsack(N, W, Baggage)))

def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict

    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        latest_dp = list(dp.items())
        for kw, kv in latest_dp:
            if kw + w <= W:
                dp[kw + w] = max(dp[kw + w], kv + v)
    ans = max(dp.values())
    return ans


N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print((d_simple_knapsack(N, W, Baggage)))

-        tmp = defaultdict(int)  # 価値の最大値を更新できた荷物の重さの情報 -        for kw, kv in list(dp.items()): +        latest_dp = list(dp.items()) +        for kw, kv in latest_dp: -                if kw + w in dp: -                    tmp[kw + w] = max(dp[kw + w], kv + v) -                else: -                    tmp[kw + w] = kv + v -        for key, value in list(tmp.items()): -            dp[key] = value +                dp[kw + w] = max(dp[kw + w], kv + v)