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

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

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

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

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

    if w<=j:

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

    else:

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

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

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

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

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

  for j in range(1,w):

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

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

    if w<=j:

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

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

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

-    for j in range(1, W + 1): +    for j in range(1, w): +        dp[i][j] = dp[i - 1][j] +    for j in range(w, W + 1): -        else: -            dp[i][j] = dp[i - 1][j]