import sys



input = sys.stdin.readline





def main():

    N, W = [int(x) for x in input().split()]

    wv = [[int(x) for x in input().split()] for _ in range(N)]



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



    for j in range(N):

        for i in range(W + 1):

            if j == 0:

                if i < wv[j][0]:

                    continue

                dp[j][i] = wv[j][1]

            else:

                if i < wv[j][0]:

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

                else:

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



    print((max(dp[-1])))



if __name__ == '__main__':

    main()

import sys



input = sys.stdin.readline





def main():

    N, W = [int(x) for x in input().split()]

    wv = [[int(x) for x in input().split()] for _ in range(N)]



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



    for j in range(N):

        for i in range(W + 1):

            if i < wv[j][0]:

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

            else:

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



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



if __name__ == '__main__':

    main()

import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    wv = [[int(x) for x in input().split()] for _ in range(N)]
    dp = [[0] * (W + 1) for j in range(N)]
    for j in range(N):
        for i in range(W + 1):
            if j == 0:
                if i < wv[j][0]:
                    continue
                dp[j][i] = wv[j][1]
            else:
                if i < wv[j][0]:
                    dp[j][i] = dp[j - 1][i]
                else:
                    dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - wv[j][0]] + wv[j][1])
    print((max(dp[-1])))


if __name__ == "__main__":
    main()

import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    wv = [[int(x) for x in input().split()] for _ in range(N)]
    dp = [[0] * (W + 1) for j in range(N + 1)]
    for j in range(N):
        for i in range(W + 1):
            if i < wv[j][0]:
                dp[j + 1][i] = dp[j][i]
            else:
                dp[j + 1][i] = max(dp[j][i], dp[j][i - wv[j][0]] + wv[j][1])
    print((dp[N][W]))


if __name__ == "__main__":
    main()

-    dp = [[0] * (W + 1) for j in range(N)] +    dp = [[0] * (W + 1) for j in range(N + 1)] -            if j == 0: -                if i < wv[j][0]: -                    continue -                dp[j][i] = wv[j][1] +            if i < wv[j][0]: +                dp[j + 1][i] = dp[j][i] -                if i < wv[j][0]: -                    dp[j][i] = dp[j - 1][i] -                else: -                    dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - wv[j][0]] + wv[j][1]) -    print((max(dp[-1]))) +                dp[j + 1][i] = max(dp[j][i], dp[j][i - wv[j][0]] + wv[j][1]) +    print((dp[N][W]))