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)

for _ in range(n):

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

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

		dp[j+w]=max(dp[j+w],dp[j]+v)

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)
for _ in range(n):
    w, v = list(map(int, input().split()))
    for j in range(W - w, -1, -1):
        dp[j + w] = max(dp[j + w], dp[j] + v)
print((dp[W]))

-for i in range(n): +for _ in range(n): -    for j in range(W, -1, -1): -        cw = j + w -        cv = dp[j] + v -        if cw <= W and dp[cw] < cv: -            dp[cw] = cv +    for j in range(W - w, -1, -1): +        dp[j + w] = max(dp[j + w], dp[j] + v)