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

items=[list(map(int,input().split())) for i in range(n)]



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

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

  for j in range(W+1):

    if j<items[i][0]:

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

    else:

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



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

    

def main():

    import numpy as np

    import sys

    input=sys.stdin.readline

    

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

    items=np.array([list(map(int,input().split())) for _ in range(n)])



    dp=np.zeros([n+1,w+1],dtype=np.int64)

    for i in range(n):

        wi=items[i][0]

        vi=items[i][1]

        dp[i+1][:wi]=dp[i][:wi]

        dp[i+1][wi:]=np.maximum(dp[i][wi:],dp[i][:-wi]+vi)

        

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

 

if __name__=='__main__':

    main()
n, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for i in range(n)]
dp = [[0] * (W + 1) for i in range(n + 1)]
for i in range(n - 1, -1, -1):
    for j in range(W + 1):
        if j < items[i][0]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - items[i][0]] + items[i][1])
print((dp[0][W]))

def main():
    import numpy as np
    import sys

    input = sys.stdin.readline
    n, w = list(map(int, input().split()))
    items = np.array([list(map(int, input().split())) for _ in range(n)])
    dp = np.zeros([n + 1, w + 1], dtype=np.int64)
    for i in range(n):
        wi = items[i][0]
        vi = items[i][1]
        dp[i + 1][:wi] = dp[i][:wi]
        dp[i + 1][wi:] = np.maximum(dp[i][wi:], dp[i][:-wi] + vi)
    print((dp[-1][-1]))


if __name__ == "__main__":
    main()

-n, W = list(map(int, input().split())) -items = [list(map(int, input().split())) for i in range(n)] -dp = [[0] * (W + 1) for i in range(n + 1)] -for i in range(n - 1, -1, -1): -    for j in range(W + 1): -        if j < items[i][0]: -            dp[i][j] = dp[i + 1][j] -        else: -            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - items[i][0]] + items[i][1]) -print((dp[0][W])) +def main(): +    import numpy as np +    import sys + +    input = sys.stdin.readline +    n, w = list(map(int, input().split())) +    items = np.array([list(map(int, input().split())) for _ in range(n)]) +    dp = np.zeros([n + 1, w + 1], dtype=np.int64) +    for i in range(n): +        wi = items[i][0] +        vi = items[i][1] +        dp[i + 1][:wi] = dp[i][:wi] +        dp[i + 1][wi:] = np.maximum(dp[i][wi:], dp[i][:-wi] + vi) +    print((dp[-1][-1])) + + +if __name__ == "__main__": +    main()