INF = float('inf')



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

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



def knapsack01(items, capW, INF):

    sumV = sum([v for w, v in items])

    dp = [0] + [INF]*sumV

    accV = 0

    for wi, vi in sorted(items, key=lambda x: x[1]):

        accV += vi

        for v in reversed(list(range(vi, min(sumV, accV)+1))):

            w0 = dp[v-vi] + wi

            if w0 < dp[v]:

                dp[v] = w0

    for v in reversed(list(range(sumV+1))):

        if dp[v] <= capW:

            return v



print((knapsack01(items, capW, INF)))

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

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



def knapsack01(items, capW):

    dp = {0: 0}

    for wi, vi in sorted(items, key=lambda x: x[1]):

        for v, w in list(dp.items()):

            v2 = v + vi

            if w+wi <= capW:

                w2 = w + wi

                if v2 in dp:

                    if w2 < dp[v2]:

                        dp[v2] = w2

                else:

                    dp[v2] = w2

    return max(dp.keys())



print((knapsack01(items, capW)))

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


def knapsack01(items, capW, INF):
    sumV = sum([v for w, v in items])
    dp = [0] + [INF] * sumV
    accV = 0
    for wi, vi in sorted(items, key=lambda x: x[1]):
        accV += vi
        for v in reversed(list(range(vi, min(sumV, accV) + 1))):
            w0 = dp[v - vi] + wi
            if w0 < dp[v]:
                dp[v] = w0
    for v in reversed(list(range(sumV + 1))):
        if dp[v] <= capW:
            return v


print((knapsack01(items, capW, INF)))

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


def knapsack01(items, capW):
    dp = {0: 0}
    for wi, vi in sorted(items, key=lambda x: x[1]):
        for v, w in list(dp.items()):
            v2 = v + vi
            if w + wi <= capW:
                w2 = w + wi
                if v2 in dp:
                    if w2 < dp[v2]:
                        dp[v2] = w2
                else:
                    dp[v2] = w2
    return max(dp.keys())


print((knapsack01(items, capW)))

-INF = float("inf") -def knapsack01(items, capW, INF): -    sumV = sum([v for w, v in items]) -    dp = [0] + [INF] * sumV -    accV = 0 +def knapsack01(items, capW): +    dp = {0: 0} -        accV += vi -        for v in reversed(list(range(vi, min(sumV, accV) + 1))): -            w0 = dp[v - vi] + wi -            if w0 < dp[v]: -                dp[v] = w0 -    for v in reversed(list(range(sumV + 1))): -        if dp[v] <= capW: -            return v +        for v, w in list(dp.items()): +            v2 = v + vi +            if w + wi <= capW: +                w2 = w + wi +                if v2 in dp: +                    if w2 < dp[v2]: +                        dp[v2] = w2 +                else: +                    dp[v2] = w2 +    return max(dp.keys()) -print((knapsack01(items, capW, INF))) +print((knapsack01(items, capW)))