def main():

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

    wv=[]

    for _ in range(n):

        wv.append(list(map(int,input().split())))

    dp=[]

    temp=[]

    for i in range(0,w+1):

        if i < wv[0][0]:

            temp.append(0)

        else:

            temp.append(wv[0][1])

    # print(temp)

    dp.append(temp)

    # print(dp)



    for i in range(1,n):

        temp=[]

        for j in range(0,w+1):

            if j < wv[i][0]:

                temp.append(dp[i-1][j])

            else:

                if j-wv[i][0] >=0:

                    temp.append(max(dp[i-1][j],dp[i-1][j-wv[i][0]] + wv[i][1]))

                else:

                    temp.append(dp[i-1][j])

        # print('temp')

        # print(temp)

        dp.append(temp)

        # print('dp')

        # print(dp)

    print((dp[n-1][w]))



if __name__=='__main__':

    main()

def main():

    n,lim_w=list(map(int,input().split()))

    wv = []

    for _ in range(n):

        tmp = list(map(int,input().split()))

        wv.append(tmp)

    dp = [[0] * (lim_w+1) for i in range(n+1)]



    for i in range(0, n):

        for w in range(0,lim_w+1):

            if w >= wv[i][0]:

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

            else:

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



    print((dp[n][lim_w]))

if __name__=='__main__':

    main()

def main():
    n, w = list(map(int, input().split()))
    wv = []
    for _ in range(n):
        wv.append(list(map(int, input().split())))
    dp = []
    temp = []
    for i in range(0, w + 1):
        if i < wv[0][0]:
            temp.append(0)
        else:
            temp.append(wv[0][1])
    # print(temp)
    dp.append(temp)
    # print(dp)
    for i in range(1, n):
        temp = []
        for j in range(0, w + 1):
            if j < wv[i][0]:
                temp.append(dp[i - 1][j])
            else:
                if j - wv[i][0] >= 0:
                    temp.append(max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1]))
                else:
                    temp.append(dp[i - 1][j])
        # print('temp')
        # print(temp)
        dp.append(temp)
        # print('dp')
        # print(dp)
    print((dp[n - 1][w]))


if __name__ == "__main__":
    main()

def main():
    n, lim_w = list(map(int, input().split()))
    wv = []
    for _ in range(n):
        tmp = list(map(int, input().split()))
        wv.append(tmp)
    dp = [[0] * (lim_w + 1) for i in range(n + 1)]
    for i in range(0, n):
        for w in range(0, lim_w + 1):
            if w >= wv[i][0]:
                dp[i + 1][w] = max(dp[i][w], dp[i][w - wv[i][0]] + wv[i][1])
            else:
                dp[i + 1][w] = dp[i][w]
    print((dp[n][lim_w]))


if __name__ == "__main__":
    main()

-    n, w = list(map(int, input().split())) +    n, lim_w = list(map(int, input().split())) -        wv.append(list(map(int, input().split()))) -    dp = [] -    temp = [] -    for i in range(0, w + 1): -        if i < wv[0][0]: -            temp.append(0) -        else: -            temp.append(wv[0][1]) -    # print(temp) -    dp.append(temp) -    # print(dp) -    for i in range(1, n): -        temp = [] -        for j in range(0, w + 1): -            if j < wv[i][0]: -                temp.append(dp[i - 1][j]) +        tmp = list(map(int, input().split())) +        wv.append(tmp) +    dp = [[0] * (lim_w + 1) for i in range(n + 1)] +    for i in range(0, n): +        for w in range(0, lim_w + 1): +            if w >= wv[i][0]: +                dp[i + 1][w] = max(dp[i][w], dp[i][w - wv[i][0]] + wv[i][1]) -                if j - wv[i][0] >= 0: -                    temp.append(max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])) -                else: -                    temp.append(dp[i - 1][j]) -        # print('temp') -        # print(temp) -        dp.append(temp) -        # print('dp') -        # print(dp) -    print((dp[n - 1][w])) +                dp[i + 1][w] = dp[i][w] +    print((dp[n][lim_w]))