

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

dp=[0]*(W+1)

L = sorted([list(map(int,input().split())) for i in range(N)])

s=0

 

for w, v in L:

    s+=w

    for j in range(min(W,s),w-1,-1):

        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v

    

print((max(dp)))
def solve(N, W, weightValues):

    dp = [0] * (W + 1)

    s = 0

    for w, v in weightValues:

        s += w

        for j in range(min(W, s), w - 1, -1):

            if dp[j - w] + v > dp[j]:

                dp[j] = dp[j - w] + v



    print((max(dp)))





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

weightValues = sorted([list(map(int, input().split())) for i in range(N)])

solve(N, W, weightValues)
N, W = list(map(int, input().split()))
dp = [0] * (W + 1)
L = sorted([list(map(int, input().split())) for i in range(N)])
s = 0
for w, v in L:
    s += w
    for j in range(min(W, s), w - 1, -1):
        if dp[j - w] + v > dp[j]:
            dp[j] = dp[j - w] + v
print((max(dp)))

def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    s = 0
    for w, v in weightValues:
        s += w
        for j in range(min(W, s), w - 1, -1):
            if dp[j - w] + v > dp[j]:
                dp[j] = dp[j - w] + v
    print((max(dp)))


N, W = list(map(int, input().split()))
weightValues = sorted([list(map(int, input().split())) for i in range(N)])
solve(N, W, weightValues)

+def solve(N, W, weightValues): +    dp = [0] * (W + 1) +    s = 0 +    for w, v in weightValues: +        s += w +        for j in range(min(W, s), w - 1, -1): +            if dp[j - w] + v > dp[j]: +                dp[j] = dp[j - w] + v +    print((max(dp))) + + -dp = [0] * (W + 1) -L = sorted([list(map(int, input().split())) for i in range(N)]) -s = 0 -for w, v in L: -    s += w -    for j in range(min(W, s), w - 1, -1): -        if dp[j - w] + v > dp[j]: -            dp[j] = dp[j - w] + v -print((max(dp))) +weightValues = sorted([list(map(int, input().split())) for i in range(N)]) +solve(N, W, weightValues)