def main():

    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 + 5) for _ in range(N + 5)]

    

    for i in range(N):

        for j in range(W):

            print()

            if j + w[i] <= W:

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

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

    

    print((max(dp[N])))





if __name__ == "__main__":

    main()
def main():

    N, Wei = 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] * (Wei + 5) for _ in range(N + 5)]

    dp[0][Wei] = 0

    for i in range(N):

        for w in range(Wei+1):

            if w >= W[i]:

                dp[i+1][w] = max(dp[i][w-W[i]] + V[i], dp[i][w])

            else:

                dp[i+1][w] = dp[i][w]



    print((dp[N][Wei]))





if __name__ == "__main__":

    main()
def main():
    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 + 5) for _ in range(N + 5)]
    for i in range(N):
        for j in range(W):
            print()
            if j + w[i] <= W:
                dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    print((max(dp[N])))


if __name__ == "__main__":
    main()

def main():
    N, Wei = 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] * (Wei + 5) for _ in range(N + 5)]
    dp[0][Wei] = 0
    for i in range(N):
        for w in range(Wei + 1):
            if w >= W[i]:
                dp[i + 1][w] = max(dp[i][w - W[i]] + V[i], dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]
    print((dp[N][Wei]))


if __name__ == "__main__":
    main()

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