def knapsack(items, num, weight):

    C = [0] * (weight + 1)

    for i in items:

        item_v, item_w = i

        for w in range(weight, 0, -1):

            if item_w <= w:

                v1 = item_v + C[w - item_w]

                v2 = C[w]

                C[w] = max(v1, v2)

    return C[weight]



import sys



file_input = sys.stdin



N, W = list(map(int, file_input.readline().split()))



items = [list(map(int, line.split())) for line in file_input]



ans = knapsack(items, N, W)



print(ans)
def knapsack(items, num, weight):

    C = [0] * (weight + 1)

    for i in items:

        item_v, item_w = i

        for w in range(weight, item_w - 1, -1):

            v1 = item_v + C[w - item_w]

            v2 = C[w]

            C[w] = max(v1, v2)

    return C[weight]



import sys



file_input = sys.stdin



N, W = list(map(int, file_input.readline().split()))



items = [list(map(int, line.split())) for line in file_input]



ans = knapsack(items, N, W)



print(ans)
def knapsack(items, num, weight):
    C = [0] * (weight + 1)
    for i in items:
        item_v, item_w = i
        for w in range(weight, 0, -1):
            if item_w <= w:
                v1 = item_v + C[w - item_w]
                v2 = C[w]
                C[w] = max(v1, v2)
    return C[weight]


import sys

file_input = sys.stdin
N, W = list(map(int, file_input.readline().split()))
items = [list(map(int, line.split())) for line in file_input]
ans = knapsack(items, N, W)
print(ans)

def knapsack(items, num, weight):
    C = [0] * (weight + 1)
    for i in items:
        item_v, item_w = i
        for w in range(weight, item_w - 1, -1):
            v1 = item_v + C[w - item_w]
            v2 = C[w]
            C[w] = max(v1, v2)
    return C[weight]


import sys

file_input = sys.stdin
N, W = list(map(int, file_input.readline().split()))
items = [list(map(int, line.split())) for line in file_input]
ans = knapsack(items, N, W)
print(ans)

-        for w in range(weight, 0, -1): -            if item_w <= w: -                v1 = item_v + C[w - item_w] -                v2 = C[w] -                C[w] = max(v1, v2) +        for w in range(weight, item_w - 1, -1): +            v1 = item_v + C[w - item_w] +            v2 = C[w] +            C[w] = max(v1, v2)