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

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



def knapsack01(items, capW):

    dp = [0] * (capW+1)

    for wi, vi in items:

        for w in reversed(list(range(wi, capW+1))):

            v0 = dp[w-wi] + vi

            if v0 > dp[w]:

                dp[w] = v0

    return max(dp)



print((knapsack01(items, capW)))

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

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



def knapsack01(items, capW):

    dp = [0] * (capW+1)

    for wi, vi in items:

        dp = [v1 if v1 >= v2 else v2 for v1, v2 in zip(dp, [0]*wi + [v+vi for v in dp[:capW-wi+1]])]

    return max(dp)



print((knapsack01(items, capW)))

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


def knapsack01(items, capW):
    dp = [0] * (capW + 1)
    for wi, vi in items:
        for w in reversed(list(range(wi, capW + 1))):
            v0 = dp[w - wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)


print((knapsack01(items, capW)))

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


def knapsack01(items, capW):
    dp = [0] * (capW + 1)
    for wi, vi in items:
        dp = [
            v1 if v1 >= v2 else v2
            for v1, v2 in zip(dp, [0] * wi + [v + vi for v in dp[: capW - wi + 1]])
        ]
    return max(dp)


print((knapsack01(items, capW)))

-        for w in reversed(list(range(wi, capW + 1))): -            v0 = dp[w - wi] + vi -            if v0 > dp[w]: -                dp[w] = v0 +        dp = [ +            v1 if v1 >= v2 else v2 +            for v1, v2 in zip(dp, [0] * wi + [v + vi for v in dp[: capW - wi + 1]]) +        ]