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)]



for i in range(n):

    for j in range(w+1):

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

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

        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)]



for i in range(n):

    for j in range(w+1):

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

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

        else:

            dp[i+1][j] = max(dp[i][j], dp[i+1][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)]
for i in range(n):
    for j in range(w + 1):
        if wv[i][0] <= j:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j])
        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)]
for i in range(n):
    for j in range(w + 1):
        if j - wv[i][0] >= 0:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j])
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
print((max(dp[-1])))

-        if wv[i][0] <= j: +        if j - wv[i][0] >= 0: -            dp[i + 1][j] = dp[i][j] +            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])