import sys

input=sys.stdin.readline

 

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

dp=[0]*(w+1)

 

def ans(n,w):

  for _ in range(n):

    c,p=list(map(int,input().split()))

    for j in range(w,c-1,-1):

      tmp=dp[j-c]+p

      if dp[j]<tmp:

        dp[j]=tmp

  return max(dp)

print((ans(n,w)))
import sys

input=sys.stdin.readline



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

dp=[0]*(w+1)

c,p=list(map(int,input().split()))

dp[c]=p



def ans(n,w):

  for _ in range(1,n):

    c,p=list(map(int,input().split()))

    for j in range(w,c,-1):

      if dp[j-c] != 0 and dp[j]<dp[j-c]+p:

        dp[j]=dp[j-c]+p

    if dp[c] < p:

      dp[c]=p

  return max(dp)

print((ans(n,w)))

import sys

input = sys.stdin.readline
n, w = list(map(int, input().split()))
dp = [0] * (w + 1)


def ans(n, w):
    for _ in range(n):
        c, p = list(map(int, input().split()))
        for j in range(w, c - 1, -1):
            tmp = dp[j - c] + p
            if dp[j] < tmp:
                dp[j] = tmp
    return max(dp)


print((ans(n, w)))

import sys

input = sys.stdin.readline
n, w = list(map(int, input().split()))
dp = [0] * (w + 1)
c, p = list(map(int, input().split()))
dp[c] = p


def ans(n, w):
    for _ in range(1, n):
        c, p = list(map(int, input().split()))
        for j in range(w, c, -1):
            if dp[j - c] != 0 and dp[j] < dp[j - c] + p:
                dp[j] = dp[j - c] + p
        if dp[c] < p:
            dp[c] = p
    return max(dp)


print((ans(n, w)))

+c, p = list(map(int, input().split())) +dp[c] = p -    for _ in range(n): +    for _ in range(1, n): -        for j in range(w, c - 1, -1): -            tmp = dp[j - c] + p -            if dp[j] < tmp: -                dp[j] = tmp +        for j in range(w, c, -1): +            if dp[j - c] != 0 and dp[j] < dp[j - c] + p: +                dp[j] = dp[j - c] + p +        if dp[c] < p: +            dp[c] = p