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 = [[None for i in range(w+1)] for j in range(n+1)]

dp[1][weight[0]] = value[0]



for i in range(1,n):

    for j in range(w+1):

        if j - weight[i] >= 0:

            if dp[i][j-weight[i]] != None and dp[i][j] != None:

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

            elif dp[i][j-weight[i]] == None and dp[i][j] != None:

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

            elif dp[i][j-weight[i]] != None and dp[i][j] == None:

                dp[i+1][j] = dp[i][j-weight[i]]+value[i]

            else:

                dp[i+1][weight[i]] = value[i]

        else:

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

            

print((max(i for i in dp[n] if i is not None)))

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 = [[None for i in range(w + 1)] for j in range(n + 1)]
dp[1][weight[0]] = value[0]
for i in range(1, n):
    for j in range(w + 1):
        if j - weight[i] >= 0:
            if dp[i][j - weight[i]] != None and dp[i][j] != None:
                dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j])
            elif dp[i][j - weight[i]] == None and dp[i][j] != None:
                dp[i + 1][j] = dp[i][j]
            elif dp[i][j - weight[i]] != None and dp[i][j] == None:
                dp[i + 1][j] = dp[i][j - weight[i]] + value[i]
            else:
                dp[i + 1][weight[i]] = value[i]
        else:
            dp[i + 1][j] = dp[i][j]
print((max(i for i in dp[n] if i is not None)))

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

-dp = [[None for i in range(w + 1)] for j in range(n + 1)] -dp[1][weight[0]] = value[0] -for i in range(1, n): +dp = [[0 for i in range(w + 1)] for j in range(n + 1)] +for i in range(1, n + 1): -        if j - weight[i] >= 0: -            if dp[i][j - weight[i]] != None and dp[i][j] != None: -                dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j]) -            elif dp[i][j - weight[i]] == None and dp[i][j] != None: -                dp[i + 1][j] = dp[i][j] -            elif dp[i][j - weight[i]] != None and dp[i][j] == None: -                dp[i + 1][j] = dp[i][j - weight[i]] + value[i] -            else: -                dp[i + 1][weight[i]] = value[i] -        else: -            dp[i + 1][j] = dp[i][j] -print((max(i for i in dp[n] if i is not None))) +        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]))