import sys



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



cf=[(0, 0)]*n



cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))



dp=[0]*(we+1)



best=0

cnt=1

lim=0



for w,c in cf:

    cnt=cnt+w

    lim=min(cnt, we-w)

    for j in range(lim, -1, -1):

        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c



print((max(dp)))
import sys



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



cf=[(0, 0)]*n



cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )



dp=[0]*(we+1)



best=0

cnt=1

lim=0



for w,c in cf:

    cnt=cnt+w

    lim=min(cnt, we-w)

    for j in range(lim, -1, -1):

        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c



print((max(dp)))
import sys

n, we = list(map(int, input().split()))
cf = [(0, 0)] * n
cf = sorted(tuple(int(x) for x in sys.stdin.readline().split()) for _ in range(n))
dp = [0] * (we + 1)
best = 0
cnt = 1
lim = 0
for w, c in cf:
    cnt = cnt + w
    lim = min(cnt, we - w)
    for j in range(lim, -1, -1):
        if dp[j + w] < (dp[j] + c):
            dp[j + w] = dp[j] + c
print((max(dp)))

import sys

n, we = list(map(int, input().split()))
cf = [(0, 0)] * n
cf = sorted([[int(x) for x in sys.stdin.readline().split()] for _ in range(n)])
dp = [0] * (we + 1)
best = 0
cnt = 1
lim = 0
for w, c in cf:
    cnt = cnt + w
    lim = min(cnt, we - w)
    for j in range(lim, -1, -1):
        if dp[j + w] < (dp[j] + c):
            dp[j + w] = dp[j] + c
print((max(dp)))

-cf = sorted(tuple(int(x) for x in sys.stdin.readline().split()) for _ in range(n)) +cf = sorted([[int(x) for x in sys.stdin.readline().split()] for _ in range(n)])