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

dp=[0]*(w+1)

for i in range(w+1):

	dp[i]=[0]*(n+1)

wt=[0]*n

val=[0]*n

for i in range(n):

	wt[i],val[i]=list(map(int,input().split()))

for i in range(1,w+1):

	for j in range(1,n+1):

		if i-wt[j-1]>=0:

			# print(i,j)

			dp[i][j]=max(val[j-1]+dp[i-wt[j-1]][j-1],dp[i][j-1])

		else:

			dp[i][j]=dp[i][j-1]

print((dp[w][n]))

# for i in range(w+1):

# 	print(dp[i])

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

dp=[0]*(w+1)

for i in range(n):

	wt,val=list(map(int,input().split()))

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

		dp[j]=max(dp[j],dp[j-wt]+val)

	# print(dp)

print((dp[w]))
n, w = list(map(int, input().split()))
dp = [0] * (w + 1)
for i in range(w + 1):
    dp[i] = [0] * (n + 1)
wt = [0] * n
val = [0] * n
for i in range(n):
    wt[i], val[i] = list(map(int, input().split()))
for i in range(1, w + 1):
    for j in range(1, n + 1):
        if i - wt[j - 1] >= 0:
            # print(i,j)
            dp[i][j] = max(val[j - 1] + dp[i - wt[j - 1]][j - 1], dp[i][j - 1])
        else:
            dp[i][j] = dp[i][j - 1]
print((dp[w][n]))
# for i in range(w+1):
# 	print(dp[i])

n, w = list(map(int, input().split()))
dp = [0] * (w + 1)
for i in range(n):
    wt, val = list(map(int, input().split()))
    for j in range(w, wt - 1, -1):
        dp[j] = max(dp[j], dp[j - wt] + val)
    # print(dp)
print((dp[w]))

-for i in range(w + 1): -    dp[i] = [0] * (n + 1) -wt = [0] * n -val = [0] * n -    wt[i], val[i] = list(map(int, input().split())) -for i in range(1, w + 1): -    for j in range(1, n + 1): -        if i - wt[j - 1] >= 0: -            # print(i,j) -            dp[i][j] = max(val[j - 1] + dp[i - wt[j - 1]][j - 1], dp[i][j - 1]) -        else: -            dp[i][j] = dp[i][j - 1] -print((dp[w][n])) -# for i in range(w+1): -# 	print(dp[i]) +    wt, val = list(map(int, input().split())) +    for j in range(w, wt - 1, -1): +        dp[j] = max(dp[j], dp[j - wt] + val) +    # print(dp) +print((dp[w]))