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

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

#WV[i][0]が重さ、WV[i][1]が価値

#配るDP

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

#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value

for i in range(n):

    for j in range(w+1):

        if WV[i][0]+j<=w and i <=n-1:

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

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

        else:

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

print((max(dp[n])))
# 貰うDP

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

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

# dp[i][w] 重さwでの最高価値

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

for j in range(w + 1):

    dp[0][j] = 0

for i in range(n):

    for j in range(w + 1):

        if j - WV[i][0] >= 0 and j - WV[i][0] <= w:

            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((dp[n][w]))

n, w = list(map(int, input().split()))
WV = [list(map(int, input().split())) for i in range(n)]
# WV[i][0]が重さ、WV[i][1]が価値
# 配るDP
dp = [[0 for i in range(w + 1)] for i in range(n + 1)]
# dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w + 1):
        if WV[i][0] + j <= w and i <= n - 1:
            dp[i + 1][j + WV[i][0]] = max(dp[i][j + WV[i][0]], dp[i][j] + WV[i][1])
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
print((max(dp[n])))

# 貰うDP
n, w = list(map(int, input().split()))
WV = [list(map(int, input().split())) for i in range(n)]
# dp[i][w] 重さwでの最高価値
dp = [[-1] * (w + 1) for i in range(n + 1)]
for j in range(w + 1):
    dp[0][j] = 0
for i in range(n):
    for j in range(w + 1):
        if j - WV[i][0] >= 0 and j - WV[i][0] <= w:
            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((dp[n][w]))

+# 貰うDP -# WV[i][0]が重さ、WV[i][1]が価値 -# 配るDP -dp = [[0 for i in range(w + 1)] for i in range(n + 1)] -# dp[i][j]はi回目(0,n-1)に重さjまで入るmax value +# dp[i][w] 重さwでの最高価値 +dp = [[-1] * (w + 1) for i in range(n + 1)] +for j in range(w + 1): +    dp[0][j] = 0 -        if WV[i][0] + j <= w and i <= n - 1: -            dp[i + 1][j + WV[i][0]] = max(dp[i][j + WV[i][0]], dp[i][j] + WV[i][1]) -            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]) +        if j - WV[i][0] >= 0 and j - WV[i][0] <= w: +            dp[i + 1][j] = max(dp[i][j - WV[i][0]] + WV[i][1], dp[i][j]) -            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]) -print((max(dp[n]))) +            dp[i + 1][j] = dp[i][j] +print((dp[n][w]))