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

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



# dp1[i][j] := 商品0 ~ i が対象

# dp2[i][j] := 商品i ~ N が対象(順番はそのまま)

# out-of-index 対策に余分に取っておく

dp1 = [[0] * (W + 1) for i in range(N + 2)]

dp2 = [[0] * (W + 1) for i in range(N + 2)]



# dp1を埋める

for i in range(N):

    wi, vi = items[i]

    for j in range(W + 1):

        if j + wi <= W:

            dp1[i + 1][j + wi] = max(dp1[i + 1][j + wi], dp1[i][j] + vi)

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



# dp2を埋める

for i in range(N + 1, 1, -1):

    wi, vi = items[i - 2]

    for j in range(W + 1):

        if j + wi <= W:

            dp2[i - 1][j + wi] = max(dp2[i - 1][j + wi], dp2[i][j] + vi)

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





# 2つのdpテーブルを使って、最後に使う商品を全探索

ans = 0

# ここからは商品を1-indexedとする

for i, (wi, vi) in enumerate(items, start=1):

    for j in range(W):

        ans = max(ans, dp1[i - 1][j] + dp2[i + 1][W - j - 1] + vi)



print(ans)

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

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



# dp1[i][j] := 商品0 ~ i が対象

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



# dpテーブルを埋める

for i in range(N):

    wi, vi = items[i]

    for j in range(W + 1):

        if j + wi <= W:

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

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





ans = 0

for i, (wi, vi) in enumerate(items):

    for j in range(W):

        ans = max(ans, dp[i][j] + vi)



print(ans)

N, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for i in range(N)]
# dp1[i][j] := 商品0 ~ i が対象
# dp2[i][j] := 商品i ~ N が対象(順番はそのまま)
# out-of-index 対策に余分に取っておく
dp1 = [[0] * (W + 1) for i in range(N + 2)]
dp2 = [[0] * (W + 1) for i in range(N + 2)]
# dp1を埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp1[i + 1][j + wi] = max(dp1[i + 1][j + wi], dp1[i][j] + vi)
        dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j])
# dp2を埋める
for i in range(N + 1, 1, -1):
    wi, vi = items[i - 2]
    for j in range(W + 1):
        if j + wi <= W:
            dp2[i - 1][j + wi] = max(dp2[i - 1][j + wi], dp2[i][j] + vi)
        dp2[i - 1][j] = max(dp2[i][j], dp2[i - 1][j])
# 2つのdpテーブルを使って、最後に使う商品を全探索
ans = 0
# ここからは商品を1-indexedとする
for i, (wi, vi) in enumerate(items, start=1):
    for j in range(W):
        ans = max(ans, dp1[i - 1][j] + dp2[i + 1][W - j - 1] + vi)
print(ans)

N, W = list(map(int, input().split()))
items = sorted([list(map(int, input().split())) for i in range(N)])
# dp1[i][j] := 商品0 ~ i が対象
dp = [[0] * (W + 1) for i in range(N + 1)]
# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
ans = 0
for i, (wi, vi) in enumerate(items):
    for j in range(W):
        ans = max(ans, dp[i][j] + vi)
print(ans)

-items = [list(map(int, input().split())) for i in range(N)] +items = sorted([list(map(int, input().split())) for i in range(N)]) -# dp2[i][j] := 商品i ~ N が対象(順番はそのまま) -# out-of-index 対策に余分に取っておく -dp1 = [[0] * (W + 1) for i in range(N + 2)] -dp2 = [[0] * (W + 1) for i in range(N + 2)] -# dp1を埋める +dp = [[0] * (W + 1) for i in range(N + 1)] +# dpテーブルを埋める -            dp1[i + 1][j + wi] = max(dp1[i + 1][j + wi], dp1[i][j] + vi) -        dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j]) -# dp2を埋める -for i in range(N + 1, 1, -1): -    wi, vi = items[i - 2] -    for j in range(W + 1): -        if j + wi <= W: -            dp2[i - 1][j + wi] = max(dp2[i - 1][j + wi], dp2[i][j] + vi) -        dp2[i - 1][j] = max(dp2[i][j], dp2[i - 1][j]) -# 2つのdpテーブルを使って、最後に使う商品を全探索 +            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi) +        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]) -# ここからは商品を1-indexedとする -for i, (wi, vi) in enumerate(items, start=1): +for i, (wi, vi) in enumerate(items): -        ans = max(ans, dp1[i - 1][j] + dp2[i + 1][W - j - 1] + vi) +        ans = max(ans, dp[i][j] + vi)