def resolve():

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

    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]



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



    for i in range(N-1,-1,-1):

        for j in range(W+1):

            w = w_v[i][0]

            v = w_v[i][1]

            if j < w_v[i][0]:

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

            else:

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

 

    print((dp[0][W]))

 

if __name__ == "__main__":

    resolve()
def resolve():

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

    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]



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



    for i in range(N):

        for j in range(W+1):

            w = w_v[i][0]

            v = w_v[i][1]

            if j < w:

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

            else:

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

 

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

 

if __name__ == "__main__":

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


if __name__ == "__main__":
    resolve()

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


if __name__ == "__main__":
    resolve()

-    for i in range(N - 1, -1, -1): +    for i in range(N): -            if j < w_v[i][0]: -                dp[i][j] = dp[i + 1][j] +            if j < w: +                dp[i + 1][j] = dp[i][j] -                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w] + v) -    print((dp[0][W])) +                dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v) +    print((dp[N][W]))