def main():

    def solve(N, W, wv):

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

        dp[0] = 0



        for i in range(N):

            wi = wv[i][0]

            vi = wv[i][1]



            for j in range(W-wi, -1, -1):

                if dp[j] == -1:

                    continue

                if dp[j+wi] < dp[j] + vi:

                    dp[j+wi] = dp[j] + vi



        return max(dp)



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

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

    print((solve(N, W, wv)))



##########

if __name__ == "__main__":

    main()

def e():

    import numpy as np



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



    dp = np.zeros(W+1, dtype=np.int64)



    for _ in range(N):

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

        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])



    print((dp[-1]))





##########

if __name__ == "__main__":

    e()

def main():
    def solve(N, W, wv):
        dp = [-1] * (W + 1)
        dp[0] = 0
        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]
            for j in range(W - wi, -1, -1):
                if dp[j] == -1:
                    continue
                if dp[j + wi] < dp[j] + vi:
                    dp[j + wi] = dp[j] + vi
        return max(dp)

    N, W = list(map(int, input().split()))
    wv = tuple(tuple(map(int, input().split())) for i in range(N))
    print((solve(N, W, wv)))


##########
if __name__ == "__main__":
    main()

def e():
    import numpy as np

    N, W = list(map(int, input().split()))
    dp = np.zeros(W + 1, dtype=np.int64)
    for _ in range(N):
        w, v = list(map(int, input().split()))
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    print((dp[-1]))


##########
if __name__ == "__main__":
    e()

-def main(): -    def solve(N, W, wv): -        dp = [-1] * (W + 1) -        dp[0] = 0 -        for i in range(N): -            wi = wv[i][0] -            vi = wv[i][1] -            for j in range(W - wi, -1, -1): -                if dp[j] == -1: -                    continue -                if dp[j + wi] < dp[j] + vi: -                    dp[j + wi] = dp[j] + vi -        return max(dp) +def e(): +    import numpy as np -    wv = tuple(tuple(map(int, input().split())) for i in range(N)) -    print((solve(N, W, wv))) +    dp = np.zeros(W + 1, dtype=np.int64) +    for _ in range(N): +        w, v = list(map(int, input().split())) +        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:]) +    print((dp[-1])) -    main() +    e()