def main():

  from collections import deque

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

  item=deque([list(map(int,input().split())) for _ in range(n)])

  DP=[[0]*(w+1) for _ in range(n+1)]

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

    itemNow=item.popleft()

    weight=itemNow[0]

    value=itemNow[1]

    for j in range(w+1):

      if j<weight:

        DP[i][j]=DP[i-1][j]

      else:

        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)

        

  print((DP[n][w]))

      

if __name__=="__main__":

  main()
def main():

  import sys

  num,capacity=list(map(int,input().split()))

  items=tuple([list(map(int,sys.stdin.readline().split())) for _ in range(num)])

  DP=[-1]*(capacity+1)

  DP[0]=0

  for item in items:

    weight=item[0]

    value=item[1]

    left=capacity-weight

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

      if DP[i]<0:

        continue

      DP[i+weight]=max(DP[i]+value,DP[i+weight])

  print((max(DP)))

      

if __name__=="__main__":

  main()
def main():
    from collections import deque

    n, w = list(map(int, input().split()))
    item = deque([list(map(int, input().split())) for _ in range(n)])
    DP = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        itemNow = item.popleft()
        weight = itemNow[0]
        value = itemNow[1]
        for j in range(w + 1):
            if j < weight:
                DP[i][j] = DP[i - 1][j]
            else:
                DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - weight] + value)
    print((DP[n][w]))


if __name__ == "__main__":
    main()

def main():
    import sys

    num, capacity = list(map(int, input().split()))
    items = tuple([list(map(int, sys.stdin.readline().split())) for _ in range(num)])
    DP = [-1] * (capacity + 1)
    DP[0] = 0
    for item in items:
        weight = item[0]
        value = item[1]
        left = capacity - weight
        for i in range(left, -1, -1):
            if DP[i] < 0:
                continue
            DP[i + weight] = max(DP[i] + value, DP[i + weight])
    print((max(DP)))


if __name__ == "__main__":
    main()

-    from collections import deque +    import sys -    n, w = list(map(int, input().split())) -    item = deque([list(map(int, input().split())) for _ in range(n)]) -    DP = [[0] * (w + 1) for _ in range(n + 1)] -    for i in range(1, n + 1): -        itemNow = item.popleft() -        weight = itemNow[0] -        value = itemNow[1] -        for j in range(w + 1): -            if j < weight: -                DP[i][j] = DP[i - 1][j] -            else: -                DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - weight] + value) -    print((DP[n][w])) +    num, capacity = list(map(int, input().split())) +    items = tuple([list(map(int, sys.stdin.readline().split())) for _ in range(num)]) +    DP = [-1] * (capacity + 1) +    DP[0] = 0 +    for item in items: +        weight = item[0] +        value = item[1] +        left = capacity - weight +        for i in range(left, -1, -1): +            if DP[i] < 0: +                continue +            DP[i + weight] = max(DP[i] + value, DP[i + weight]) +    print((max(DP)))