



def main():

    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10000000)

    from collections import Counter, deque

    #from collections import defaultdict

    from itertools import combinations, permutations

    #from itertools import accumulate, product

    from bisect import bisect_left,bisect_right

    from math import floor, ceil

    #from operator import itemgetter



    #mod = 1000000007



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

    w = [0]*N

    v = [0]*N

    for i in range(N):

        w[i], v[i] = list(map(int, input().split()))

    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(N):

        for j in range(W+1):

            if w[i]<=j:

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

            else:

                dp[i+1][j] = dp[i][j]

    print((dp[N][W]))

    



if __name__ == '__main__':

    main()
def main():

    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10000000)

    from collections import Counter, deque

    #from collections import defaultdict

    from itertools import combinations, permutations

    #from itertools import accumulate, product

    from bisect import bisect_left,bisect_right

    from math import floor, ceil

    #from operator import itemgetter



    #mod = 1000000007

    

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

    wv = [tuple(map(int,input().split())) for i in range(N)]

    dp = [0]*(W+1)

    for i in range(N):

        for j in range(W, wv[i][0]-1, -1):

            dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

    print((max(dp)))



if __name__ == '__main__':

    main()

def main():
    import sys

    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque

    # from collections import defaultdict
    from itertools import combinations, permutations

    # from itertools import accumulate, product
    from bisect import bisect_left, bisect_right
    from math import floor, ceil

    # from operator import itemgetter
    # mod = 1000000007
    N, W = list(map(int, input().split()))
    w = [0] * N
    v = [0] * N
    for i in range(N):
        w[i], v[i] = list(map(int, input().split()))
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if w[i] <= j:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
            else:
                dp[i + 1][j] = dp[i][j]
    print((dp[N][W]))


if __name__ == "__main__":
    main()

def main():
    import sys

    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque

    # from collections import defaultdict
    from itertools import combinations, permutations

    # from itertools import accumulate, product
    from bisect import bisect_left, bisect_right
    from math import floor, ceil

    # from operator import itemgetter
    # mod = 1000000007
    N, W = list(map(int, input().split()))
    wv = [tuple(map(int, input().split())) for i in range(N)]
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, wv[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - wv[i][0]] + wv[i][1])
    print((max(dp)))


if __name__ == "__main__":
    main()

-    w = [0] * N -    v = [0] * N +    wv = [tuple(map(int, input().split())) for i in range(N)] +    dp = [0] * (W + 1) -        w[i], v[i] = list(map(int, input().split())) -    dp = [[0] * (W + 1) for _ in range(N + 1)] -    for i in range(N): -        for j in range(W + 1): -            if w[i] <= j: -                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) -            else: -                dp[i + 1][j] = dp[i][j] -    print((dp[N][W])) +        for j in range(W, wv[i][0] - 1, -1): +            dp[j] = max(dp[j], dp[j - wv[i][0]] + wv[i][1]) +    print((max(dp)))