import sys

import math

import itertools





# \n





def input():

    return sys.stdin.readline().rstrip()





def main():

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



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



    for i in range(N):

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

        for j in range(WW+1):

            if w<=j:

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

            else:

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



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





if __name__ == "__main__":

    main()

import sys





# \n

def input():

    return sys.stdin.readline().rstrip()





def main():

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

    dp =[0] *(W+1)

    for i in range(N):

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



        for i in range(W,w-1,-1):

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







    print((max(dp)))











if __name__ == "__main__":

    main()

import sys
import math
import itertools

# \n
def input():
    return sys.stdin.readline().rstrip()


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


if __name__ == "__main__":
    main()

import sys

# \n
def input():
    return sys.stdin.readline().rstrip()


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


if __name__ == "__main__":
    main()

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