# -*- coding: utf-8 -*-

"""

D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d



"""

import sys





def solve(N, W, items):

    ans = {0: 0}

    for w, v in items:

        u = dict()

        for x, y in list(ans.items()):

            if x+w <= W and ans.get(x+w, 0) < y+v:

                u[x+w] = y+v

        ans.update(u)

    return max([v for v in list(ans.values())])





def main(args):

    N, W = list(map(int, input().split()))

    items = [[int(i) for i in input().split()] for _ in range(N)]

    ans = solve(N, W, items)

    print(ans)





if __name__ == '__main__':

    main(sys.argv[1:])
# -*- coding: utf-8 -*-

"""

D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d



"""

import sys





def solve(N, W, items):

    dp = [0-1] * (W+1)

    dp[0] = 0

    for w, v in items:

        for i in range(W, w-1, -1):

            if dp[i-w] != -1:

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

    return max(dp)







def main(args):

    N, W = list(map(int, input().split()))

    items = [[int(i) for i in input().split()] for _ in range(N)]

    ans = solve(N, W, items)

    print(ans)





if __name__ == '__main__':

    main(sys.argv[1:])
# -*- coding: utf-8 -*-
"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d
"""
import sys


def solve(N, W, items):
    ans = {0: 0}
    for w, v in items:
        u = dict()
        for x, y in list(ans.items()):
            if x + w <= W and ans.get(x + w, 0) < y + v:
                u[x + w] = y + v
        ans.update(u)
    return max([v for v in list(ans.values())])


def main(args):
    N, W = list(map(int, input().split()))
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == "__main__":
    main(sys.argv[1:])

# -*- coding: utf-8 -*-
"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d
"""
import sys


def solve(N, W, items):
    dp = [0 - 1] * (W + 1)
    dp[0] = 0
    for w, v in items:
        for i in range(W, w - 1, -1):
            if dp[i - w] != -1:
                dp[i] = max(dp[i], dp[i - w] + v)
    return max(dp)


def main(args):
    N, W = list(map(int, input().split()))
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == "__main__":
    main(sys.argv[1:])

-    ans = {0: 0} +    dp = [0 - 1] * (W + 1) +    dp[0] = 0 -        u = dict() -        for x, y in list(ans.items()): -            if x + w <= W and ans.get(x + w, 0) < y + v: -                u[x + w] = y + v -        ans.update(u) -    return max([v for v in list(ans.values())]) +        for i in range(W, w - 1, -1): +            if dp[i - w] != -1: +                dp[i] = max(dp[i], dp[i - w] + v) +    return max(dp)