# D - Knapsack 1

from collections import defaultdict





def main():

    N, W, *WV = list(map(int, open(0).read().split()))

    dp = defaultdict(int)

    dp[0] = 0

    for w, v in zip(*[iter(WV)] * 2):

        for cur_w, cur_v in tuple(dp.items()):

            if w + cur_w <= W:

                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v)

    print((max(dp.values())))





if __name__ == "__main__":

    main()

# D - Knapsack 1

def solve_knapsack(weight_limit: int, weights: list, values: list) -> int:

    dp = [0] * (weight_limit + 1)  # dp[i] := optimum value at weight i

    for w, v in zip(weights, values):

        for cur_w in range(weight_limit, w - 1, -1):

            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)

    return dp[-1]





def main():

    N, W, *WV = list(map(int, open(0).read().split()))

    print((solve_knapsack(W, WV[::2], WV[1::2])))





if __name__ == "__main__":

    main()

# D - Knapsack 1
from collections import defaultdict


def main():
    N, W, *WV = list(map(int, open(0).read().split()))
    dp = defaultdict(int)
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_w, cur_v in tuple(dp.items()):
            if w + cur_w <= W:
                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v)
    print((max(dp.values())))


if __name__ == "__main__":
    main()

# D - Knapsack 1
def solve_knapsack(weight_limit: int, weights: list, values: list) -> int:
    dp = [0] * (weight_limit + 1)  # dp[i] := optimum value at weight i
    for w, v in zip(weights, values):
        for cur_w in range(weight_limit, w - 1, -1):
            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)
    return dp[-1]


def main():
    N, W, *WV = list(map(int, open(0).read().split()))
    print((solve_knapsack(W, WV[::2], WV[1::2])))


if __name__ == "__main__":
    main()

-from collections import defaultdict +def solve_knapsack(weight_limit: int, weights: list, values: list) -> int: +    dp = [0] * (weight_limit + 1)  # dp[i] := optimum value at weight i +    for w, v in zip(weights, values): +        for cur_w in range(weight_limit, w - 1, -1): +            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v) +    return dp[-1] -    dp = defaultdict(int) -    dp[0] = 0 -    for w, v in zip(*[iter(WV)] * 2): -        for cur_w, cur_v in tuple(dp.items()): -            if w + cur_w <= W: -                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v) -    print((max(dp.values()))) +    print((solve_knapsack(W, WV[::2], WV[1::2])))