# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値



N, W = list(map(int, input().split()))

items = [tuple(map(int, input().split())) for i in range(N)]



dp = [[0 for w_sum in range(W+100)] for i in range(N+100)]



for i in range(N):

    for w_sum in range(W+1):



        # i-1番目の品物を選ぶ場合

        # 重量的に入れられるなら入れてみる

        if w_sum-items[i][0] >= 0:

            dp[i+1][w_sum] = max(dp[i+1][w_sum],

                                 dp[i][w_sum-items[i][0]]+items[i][1])



        # i-1番目の品物を選ばない場合

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



print((dp[N][W]))

# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N, W = list(map(int, input().split()))

items = [tuple(map(int, input().split())) for i in range(N)]



dp = [[0 for w_sum in range(W+1)] for i in range(N+1)]



for i in range(N):

    for w_sum in range(W+1):



        # i-1番目の品物を選ぶ場合

        # 重量的に入れられるなら入れてみる

        if w_sum+items[i][0] <= W:

            dp[i+1][w_sum+items[i][0]] = max(dp[i+1][w_sum+items[i][0]],

                                             dp[i][w_sum]+items[i][1])



        # i-1番目の品物を選ばない場合

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



ans = 0

for w in range(W+1):

    ans = max(ans, dp[N][w])

print(ans)

# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, W = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0 for w_sum in range(W + 100)] for i in range(N + 100)]
for i in range(N):
    for w_sum in range(W + 1):
        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum - items[i][0] >= 0:
            dp[i + 1][w_sum] = max(
                dp[i + 1][w_sum], dp[i][w_sum - items[i][0]] + items[i][1]
            )
        # i-1番目の品物を選ばない場合
        dp[i + 1][w_sum] = max(dp[i + 1][w_sum], dp[i][w_sum])
print((dp[N][W]))

# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, W = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0 for w_sum in range(W + 1)] for i in range(N + 1)]
for i in range(N):
    for w_sum in range(W + 1):
        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum + items[i][0] <= W:
            dp[i + 1][w_sum + items[i][0]] = max(
                dp[i + 1][w_sum + items[i][0]], dp[i][w_sum] + items[i][1]
            )
        # i-1番目の品物を選ばない場合
        dp[i + 1][w_sum] = max(dp[i + 1][w_sum], dp[i][w_sum])
ans = 0
for w in range(W + 1):
    ans = max(ans, dp[N][w])
print(ans)

-# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値 +# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値 -dp = [[0 for w_sum in range(W + 100)] for i in range(N + 100)] +dp = [[0 for w_sum in range(W + 1)] for i in range(N + 1)] -        if w_sum - items[i][0] >= 0: -            dp[i + 1][w_sum] = max( -                dp[i + 1][w_sum], dp[i][w_sum - items[i][0]] + items[i][1] +        if w_sum + items[i][0] <= W: +            dp[i + 1][w_sum + items[i][0]] = max( +                dp[i + 1][w_sum + items[i][0]], dp[i][w_sum] + items[i][1] -print((dp[N][W])) +ans = 0 +for w in range(W + 1): +    ans = max(ans, dp[N][w]) +print(ans)