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

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):

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

  for j in range(W+1):

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

    if j+w<=W:

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

print((max(dp[N])))
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-w,-1,-1):

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

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

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 - w, -1, -1):
        dp[j + w] = max(dp[j] + v, dp[j + w])
print((max(dp)))

-dp = [[0] * (W + 1) for _ in range(N + 1)] +dp = [0] * (W + 1) -    for j in range(W + 1): -        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]) -        if j + w <= W: -            dp[i + 1][j + w] = max(dp[i][j] + v, dp[i + 1][j + w]) -print((max(dp[N]))) +    for j in range(W - w, -1, -1): +        dp[j + w] = max(dp[j] + v, dp[j + w]) +print((max(dp)))