def knapsack(items, num, weight):

    r = weight + 1

    C = [[0] * r for i in range(num + 1)]

    

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

        item_v, item_w = item

        for w in range(1, r):

            if item_w <= w:

                v1 = item_v + C[i - 1][w - item_w]

                v2 = C[i - 1][w]

                C[i][w] = max(v1, v2)

            else:

                C[i][w] = C[i - 1][w]

    return C[-1][-1]



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):
    r = weight + 1
    C = [[0] * r for i in range(num + 1)]
    for i, item in enumerate(items, start=1):
        item_v, item_w = item
        for w in range(1, r):
            if item_w <= w:
                v1 = item_v + C[i - 1][w - item_w]
                v2 = C[i - 1][w]
                C[i][w] = max(v1, v2)
            else:
                C[i][w] = C[i - 1][w]
    return C[-1][-1]


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)

-    r = weight + 1 -    C = [[0] * r for i in range(num + 1)] -    for i, item in enumerate(items, start=1): -        item_v, item_w = item -        for w in range(1, r): +    C = [0] * (weight + 1) +    for i in items: +        item_v, item_w = i +        for w in range(weight, 0, -1): -                v1 = item_v + C[i - 1][w - item_w] -                v2 = C[i - 1][w] -                C[i][w] = max(v1, v2) -            else: -                C[i][w] = C[i - 1][w] -    return C[-1][-1] +                v1 = item_v + C[w - item_w] +                v2 = C[w] +                C[w] = max(v1, v2) +    return C[weight]