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

wv=[[0,0]]+[list(map(int,input().split())) for _ in range(N)]



dp=[[0 for i in range(W+1)] for j in range(N+1)]



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

    for j in range(W+1):

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

        if j - wv[i][0] >= 0:

            dp[i][j]=max(dp[i][j],dp[i-1][j-wv[i][0]]+wv[i][1])



            

print((max(dp[N])))

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

w = []

v = []

for i in range(N):

	wi, vi = list(map(int, input().split()))

	w.append(wi)

	v.append(vi)



dp = [0] * (W + 1)

dp[w[0]] = v[0]



for i in range(1, N):

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

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

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

print((max(dp)))
N, W = list(map(int, input().split()))
wv = [[0, 0]] + [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(1, N + 1):
    for j in range(W + 1):
        dp[i][j] = dp[i - 1][j]
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
print((max(dp[N])))

N, W = list(map(int, input().split()))
w = []
v = []
for i in range(N):
    wi, vi = list(map(int, input().split()))
    w.append(wi)
    v.append(vi)
dp = [0] * (W + 1)
dp[w[0]] = v[0]
for i in range(1, N):
    for j in range(W, -1, -1):
        if j - w[i] >= 0 and dp[j - w[i]] + v[i] > dp[j]:
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print((max(dp)))

-wv = [[0, 0]] + [list(map(int, input().split())) for _ in range(N)] -dp = [[0 for i in range(W + 1)] for j in range(N + 1)] -for i in range(1, N + 1): -    for j in range(W + 1): -        dp[i][j] = dp[i - 1][j] -        if j - wv[i][0] >= 0: -            dp[i][j] = max(dp[i][j], dp[i - 1][j - wv[i][0]] + wv[i][1]) -print((max(dp[N]))) +w = [] +v = [] +for i in range(N): +    wi, vi = list(map(int, input().split())) +    w.append(wi) +    v.append(vi) +dp = [0] * (W + 1) +dp[w[0]] = v[0] +for i in range(1, N): +    for j in range(W, -1, -1): +        if j - w[i] >= 0 and dp[j - w[i]] + v[i] > dp[j]: +            dp[j] = max(dp[j], dp[j - w[i]] + v[i]) +print((max(dp)))