n, cap = list(map(int, input().split()))

dp = [None] * (cap + 1)

dp[0] = 0



for _ in range(n):

    v, w = list(map(int, input().split()))

    for k in range(cap - w, -1, -1):

        tmp_before_v = dp[k]

        if tmp_before_v == None:

            continue

        tmp_after_v, new_v = dp[k + w], tmp_before_v + v

        if tmp_after_v == None or tmp_after_v < new_v:

            dp[k + w] = new_v



print((max([_f for _f in dp if _f])))
n, cap = list(map(int, input().split()))

dp = [0] * (cap + 1)



for _ in range(n):

    v, w = list(map(int, input().split()))

    for k in range(cap - w, -1, -1):

        new_v = dp[k] + v

        if dp[k + w] < new_v:

            dp[k + w] = new_v



print((max(dp)))
n, cap = list(map(int, input().split()))
dp = [None] * (cap + 1)
dp[0] = 0
for _ in range(n):
    v, w = list(map(int, input().split()))
    for k in range(cap - w, -1, -1):
        tmp_before_v = dp[k]
        if tmp_before_v == None:
            continue
        tmp_after_v, new_v = dp[k + w], tmp_before_v + v
        if tmp_after_v == None or tmp_after_v < new_v:
            dp[k + w] = new_v
print((max([_f for _f in dp if _f])))

n, cap = list(map(int, input().split()))
dp = [0] * (cap + 1)
for _ in range(n):
    v, w = list(map(int, input().split()))
    for k in range(cap - w, -1, -1):
        new_v = dp[k] + v
        if dp[k + w] < new_v:
            dp[k + w] = new_v
print((max(dp)))

-dp = [None] * (cap + 1) -dp[0] = 0 +dp = [0] * (cap + 1) -        tmp_before_v = dp[k] -        if tmp_before_v == None: -            continue -        tmp_after_v, new_v = dp[k + w], tmp_before_v + v -        if tmp_after_v == None or tmp_after_v < new_v: +        new_v = dp[k] + v +        if dp[k + w] < new_v: -print((max([_f for _f in dp if _f]))) +print((max(dp)))