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 dp[-1]

print((ans(n,w)))
N,W=list(map(int,input().split()))



def solve_knapsack(capacity):

    # basic checks

 

    dp = [0]*(capacity + 1)

    # populate the capacity = 0 columns, with '0' capacity we have '0' profit



    for i in range(0, N):

        weights,profits = list(map(int,input().split()))

        for c in range(capacity, weights-1, -1):

            tmp = profits + dp[c - weights]

            if tmp > dp[c]: dp[c] = tmp

 

    # maximum profit will be at the bottom-right corner.

    return dp[capacity]

  

def main():

 

    res = solve_knapsack(W)

 

    print(res)

if __name__ == "__main__":

	main()
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 dp[-1]


print((ans(n, w)))

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


def solve_knapsack(capacity):
    # basic checks
    dp = [0] * (capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    for i in range(0, N):
        weights, profits = list(map(int, input().split()))
        for c in range(capacity, weights - 1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]:
                dp[c] = tmp
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]


def main():
    res = solve_knapsack(W)
    print(res)


if __name__ == "__main__":
    main()

-import sys - -input = sys.stdin.readline -n, w = list(map(int, input().split())) -dp = [0] * (w + 1) +N, W = list(map(int, input().split())) -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 dp[-1] +def solve_knapsack(capacity): +    # basic checks +    dp = [0] * (capacity + 1) +    # populate the capacity = 0 columns, with '0' capacity we have '0' profit +    for i in range(0, N): +        weights, profits = list(map(int, input().split())) +        for c in range(capacity, weights - 1, -1): +            tmp = profits + dp[c - weights] +            if tmp > dp[c]: +                dp[c] = tmp +    # maximum profit will be at the bottom-right corner. +    return dp[capacity] -print((ans(n, w))) +def main(): +    res = solve_knapsack(W) +    print(res) + + +if __name__ == "__main__": +    main()