def main():

    import sys

    input = sys.stdin.readline

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

    l = [list(map(int,input().split())) for i in range(n)]



    dp = [[0]*(w+1) for i in range(n+1)]

    for i in range(1,n+1):

        for j in range(w+1):

            if j-l[i-1][0] >= 0:

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

            else:

                dp[i][j] = dp[i-1][j]

    print((dp[n][w]))

if __name__ == "__main__":

    main()
def main():

    import numpy as np

    import sys

    input = sys.stdin.readline



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

    l = [list(map(int,input().split())) for i in range(n)]



    dp = np.zeros((n+1,w+1),dtype="int64")

    for i in range(n):

        dp[i+1][:l[i][0]] = dp[i][:l[i][0]]

        dp[i+1][l[i][0]:] = np.maximum(dp[i][l[i][0]:],dp[i][:-l[i][0]]+l[i][1])

    print((dp[n][w]))



if __name__ == "__main__":

    main()
def main():
    import sys

    input = sys.stdin.readline
    n, w = list(map(int, input().split()))
    l = [list(map(int, input().split())) for i in range(n)]
    dp = [[0] * (w + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(w + 1):
            if j - l[i - 1][0] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - l[i - 1][0]] + l[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]
    print((dp[n][w]))


if __name__ == "__main__":
    main()

def main():
    import numpy as np
    import sys

    input = sys.stdin.readline
    n, w = list(map(int, input().split()))
    l = [list(map(int, input().split())) for i in range(n)]
    dp = np.zeros((n + 1, w + 1), dtype="int64")
    for i in range(n):
        dp[i + 1][: l[i][0]] = dp[i][: l[i][0]]
        dp[i + 1][l[i][0] :] = np.maximum(dp[i][l[i][0] :], dp[i][: -l[i][0]] + l[i][1])
    print((dp[n][w]))


if __name__ == "__main__":
    main()

+    import numpy as np -    dp = [[0] * (w + 1) for i in range(n + 1)] -    for i in range(1, n + 1): -        for j in range(w + 1): -            if j - l[i - 1][0] >= 0: -                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - l[i - 1][0]] + l[i - 1][1]) -            else: -                dp[i][j] = dp[i - 1][j] +    dp = np.zeros((n + 1, w + 1), dtype="int64") +    for i in range(n): +        dp[i + 1][: l[i][0]] = dp[i][: l[i][0]] +        dp[i + 1][l[i][0] :] = np.maximum(dp[i][l[i][0] :], dp[i][: -l[i][0]] + l[i][1])