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

weight = [0 for i in range(n)]

value = [0 for i in range(n)]

for i in range(n):

    weight[i],value[i] = list(map(int,input().split()))

    



#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値

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



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

    for j in range(w+1):

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

        if(j - weight[i-1] >= 0):

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

            

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

weight = [0 for i in range(n)]

value = [0 for i in range(n)]

for i in range(n):

    weight[i],value[i] = list(map(int,input().split()))

    

 

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値

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

 

for i in range(n):

    for j in range(w+1):

        if j - weight[i] >= 0:

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

        else:

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

            

print((dp[n][w]))
n, w = list(map(int, input().split()))
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i], value[i] = list(map(int, input().split()))
# dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        if j - weight[i - 1] >= 0:
            dp[i][j] = max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i][j])
print((dp[n][w]))

n, w = list(map(int, input().split()))
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i], value[i] = list(map(int, input().split()))
# dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - weight[i] >= 0:
            dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print((dp[n][w]))

-for i in range(1, n + 1): +for i in range(n): -        dp[i][j] = max(dp[i][j], dp[i - 1][j]) -        if j - weight[i - 1] >= 0: -            dp[i][j] = max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i][j]) +        if j - weight[i] >= 0: +            dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j]) +        else: +            dp[i + 1][j] = dp[i][j]