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

inf = float("inf")

dp = [[-inf]*(w+1) for _ in range(n+1)]

for j in range(w+1):

    dp[0][j] = 0

for i in range(n):

    s,t = list(map(int,input().split()))

    for l in range(w+1):

        if l-s >=0:

            dp[i+1][l] = max(dp[i][l],dp[i][l-s]+t)

        else:

            dp[i+1][l] = dp[i][l]

print((dp[-1][w]))        
n,w = list(map(int,input().split()))

ls = [list(map(int,input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):

    for p in range(w+1):

        if p >= ls[i][0]:

            dp[i+1][p] = max(dp[i][p],dp[i][p-ls[i][0]]+ls[i][1])

        else:

            dp[i+1][p] = dp[i][p]

print((dp[n][w]))
n, w = list(map(int, input().split()))
inf = float("inf")
dp = [[-inf] * (w + 1) for _ in range(n + 1)]
for j in range(w + 1):
    dp[0][j] = 0
for i in range(n):
    s, t = list(map(int, input().split()))
    for l in range(w + 1):
        if l - s >= 0:
            dp[i + 1][l] = max(dp[i][l], dp[i][l - s] + t)
        else:
            dp[i + 1][l] = dp[i][l]
print((dp[-1][w]))

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

-inf = float("inf") -dp = [[-inf] * (w + 1) for _ in range(n + 1)] -for j in range(w + 1): -    dp[0][j] = 0 +ls = [list(map(int, input().split())) for _ in range(n)] +dp = [[0] * (w + 1) for _ in range(n + 1)] -    s, t = list(map(int, input().split())) -    for l in range(w + 1): -        if l - s >= 0: -            dp[i + 1][l] = max(dp[i][l], dp[i][l - s] + t) +    for p in range(w + 1): +        if p >= ls[i][0]: +            dp[i + 1][p] = max(dp[i][p], dp[i][p - ls[i][0]] + ls[i][1]) -            dp[i + 1][l] = dp[i][l] -print((dp[-1][w])) +            dp[i + 1][p] = dp[i][p] +print((dp[n][w]))