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

dp=[0]*(W+1)

dd=dp.copy()

for i in range(n):

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

	for j in range(W):

		cw=j+w

		cv=dp[j]+v

		if cw <=W and dd[cw]<cv:

			dd[cw]=cv

	dp=dd.copy()

print((dp[W]))
n,W=list(map(int,input().split()))

dp=[0]*(W+1)

for i in range(n):

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

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

		cw=j+w

		cv=dp[j]+v

		if cw <=W and dp[cw]<cv:

			dp[cw]=cv

print((dp[W]))
n, W = list(map(int, input().split()))
dp = [0] * (W + 1)
dd = dp.copy()
for i in range(n):
    w, v = list(map(int, input().split()))
    for j in range(W):
        cw = j + w
        cv = dp[j] + v
        if cw <= W and dd[cw] < cv:
            dd[cw] = cv
    dp = dd.copy()
print((dp[W]))

n, W = list(map(int, input().split()))
dp = [0] * (W + 1)
for i in range(n):
    w, v = list(map(int, input().split()))
    for j in range(W, -1, -1):
        cw = j + w
        cv = dp[j] + v
        if cw <= W and dp[cw] < cv:
            dp[cw] = cv
print((dp[W]))

-dd = dp.copy() -    for j in range(W): +    for j in range(W, -1, -1): -        if cw <= W and dd[cw] < cv: -            dd[cw] = cv -    dp = dd.copy() +        if cw <= W and dp[cw] < cv: +            dp[cw] = cv