def solve(items, n, w):

    f = [[0] * (w + 1) for _ in range(n + 1)]

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

        wi, vi = items[i-1]

        for j in range(w + 1):

            f[i][j] = f[i-1][j]

            if j >= wi:

                f[i][j] = max(f[i][j], f[i-1][j-wi] + vi)

    return f[n][w]





def main():

    inp = lambda: [int(x) for x in input().split()]

    n, w = inp()

    items = [inp() for _ in range(n)]

    print((solve(items, n, w)))





if __name__ == '__main__':

    main()

def solve(items, n, w):

    dp = [0] * (w+1)

    for i in range(n):

        wi, vi = items[i]

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

            dp[j] = max(dp[j], dp[j-wi] + vi)



    return dp[w]





def main():

    inp = lambda: [int(x) for x in input().split()]

    n, w = inp()

    items = [inp() for _ in range(n)]

    print((solve(items, n, w)))





if __name__ == '__main__':

    main()

def solve(items, n, w):
    f = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = items[i - 1]
        for j in range(w + 1):
            f[i][j] = f[i - 1][j]
            if j >= wi:
                f[i][j] = max(f[i][j], f[i - 1][j - wi] + vi)
    return f[n][w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print((solve(items, n, w)))


if __name__ == "__main__":
    main()

def solve(items, n, w):
    dp = [0] * (w + 1)
    for i in range(n):
        wi, vi = items[i]
        for j in range(w, wi - 1, -1):
            dp[j] = max(dp[j], dp[j - wi] + vi)
    return dp[w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print((solve(items, n, w)))


if __name__ == "__main__":
    main()

-    f = [[0] * (w + 1) for _ in range(n + 1)] -    for i in range(1, n + 1): -        wi, vi = items[i - 1] -        for j in range(w + 1): -            f[i][j] = f[i - 1][j] -            if j >= wi: -                f[i][j] = max(f[i][j], f[i - 1][j - wi] + vi) -    return f[n][w] +    dp = [0] * (w + 1) +    for i in range(n): +        wi, vi = items[i] +        for j in range(w, wi - 1, -1): +            dp[j] = max(dp[j], dp[j - wi] + vi) +    return dp[w]