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

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



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

dp[0][0] = 0



for i in range(n):

    for j in range(w+1):

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

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

        else:

            dp[i+1][j] = dp[i][j]



print((max(dp[-1])))



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

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



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

dp[0][0] = 0



for i in range(n):

    for j in range(w+1):

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

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

        else:

            dp[i+1][j] = dp[i][j]



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

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

-dp = [[-float("inf") for _ in range(w + 1)] for _ in range(n + 1)] +dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)] -print((max(dp[-1]))) +print((dp[-1][-1]))