def p_d():

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

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



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

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

        for j in range(1, W + 1):

            if j - w >= 0:

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

            else:

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



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





if __name__ == '__main__':

    p_d()

def p_e():

    """

    ナップサック問題（制約厳しい版） 

    """

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

    dp = [0] * (W + 1)

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

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

        NEXT = [0] * (W + 1)

        for j in range(1, W + 1):

            if j - w >= 0:

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

            else:

                NEXT[j] = dp[j]

        dp = NEXT



    print((max(NEXT)))





if __name__ == '__main__':

    p_e()

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


if __name__ == "__main__":
    p_d()

def p_e():
    """
    ナップサック問題（制約厳しい版）
    """
    N, W = list(map(int, input().split()))
    dp = [0] * (W + 1)
    for i in range(1, N + 1):
        w, v = list(map(int, input().split()))
        NEXT = [0] * (W + 1)
        for j in range(1, W + 1):
            if j - w >= 0:
                NEXT[j] = max(v + dp[j - w], dp[j])
            else:
                NEXT[j] = dp[j]
        dp = NEXT
    print((max(NEXT)))


if __name__ == "__main__":
    p_e()

-def p_d(): +def p_e(): +    """ +    ナップサック問題（制約厳しい版） +    """ -    dp = [[0] * (W + 1) for _ in range(N + 1)] +    dp = [0] * (W + 1) +        NEXT = [0] * (W + 1) -                dp[i][j] = max(v + dp[i - 1][j - w], dp[i - 1][j]) +                NEXT[j] = max(v + dp[j - w], dp[j]) -                dp[i][j] = max(dp[i - 1][j], dp[i][j]) -    print((max(dp[N]))) +                NEXT[j] = dp[j] +        dp = NEXT +    print((max(NEXT))) -    p_d() +    p_e()