# python template for atcoder1

import sys

sys.setrecursionlimit(10**9)

input = sys.stdin.readline



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

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

dp = [[0]*(W+1) for _ in range(N)]



# init

first_item = items[0]

for i in range(W+1):

    if i >= first_item[0]:

        dp[0][i] = first_item[1]



# update

for i in range(1, N):

    for w in range(W+1):

        if w-items[i][0] >= 0:

            dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i][0]]+items[i][1])

        else:

            dp[i][w] = dp[i-1][w]



print((max(dp[N-1])))

# python template for atcoder1

import sys

sys.setrecursionlimit(10**9)

input = sys.stdin.readline



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

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





def solve():

    dp = [[0]*(W+1) for _ in range(N+1)]



    # init

    # update

    for i in range(1, N+1):

        for w in range(W+1):

            if w-items[i-1][0] >= 0:

                dp[i][w] = max(dp[i-1][w], dp[i-1]

                               [w-items[i-1][0]]+items[i-1][1])

            else:

                dp[i][w] = dp[i-1][w]



    print((max(dp[N])))





def solve2():

    dp = [0]*(W+1)

    for i in range(N):

        for w in reversed(list(range(W+1))):

            if w-items[i][0] >= 0:

                dp[w] = max(dp[w], dp[w-items[i][0]]+items[i][1])

    print((dp[-1]))





solve2()

# python template for atcoder1
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N)]
# init
first_item = items[0]
for i in range(W + 1):
    if i >= first_item[0]:
        dp[0][i] = first_item[1]
# update
for i in range(1, N):
    for w in range(W + 1):
        if w - items[i][0] >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - items[i][0]] + items[i][1])
        else:
            dp[i][w] = dp[i - 1][w]
print((max(dp[N - 1])))

# python template for atcoder1
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(N)]


def solve():
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    # init
    # update
    for i in range(1, N + 1):
        for w in range(W + 1):
            if w - items[i - 1][0] >= 0:
                dp[i][w] = max(
                    dp[i - 1][w], dp[i - 1][w - items[i - 1][0]] + items[i - 1][1]
                )
            else:
                dp[i][w] = dp[i - 1][w]
    print((max(dp[N])))


def solve2():
    dp = [0] * (W + 1)
    for i in range(N):
        for w in reversed(list(range(W + 1))):
            if w - items[i][0] >= 0:
                dp[w] = max(dp[w], dp[w - items[i][0]] + items[i][1])
    print((dp[-1]))


solve2()

-dp = [[0] * (W + 1) for _ in range(N)] -# init -first_item = items[0] -for i in range(W + 1): -    if i >= first_item[0]: -        dp[0][i] = first_item[1] -# update -for i in range(1, N): -    for w in range(W + 1): -        if w - items[i][0] >= 0: -            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - items[i][0]] + items[i][1]) -        else: -            dp[i][w] = dp[i - 1][w] -print((max(dp[N - 1]))) + + +def solve(): +    dp = [[0] * (W + 1) for _ in range(N + 1)] +    # init +    # update +    for i in range(1, N + 1): +        for w in range(W + 1): +            if w - items[i - 1][0] >= 0: +                dp[i][w] = max( +                    dp[i - 1][w], dp[i - 1][w - items[i - 1][0]] + items[i - 1][1] +                ) +            else: +                dp[i][w] = dp[i - 1][w] +    print((max(dp[N]))) + + +def solve2(): +    dp = [0] * (W + 1) +    for i in range(N): +        for w in reversed(list(range(W + 1))): +            if w - items[i][0] >= 0: +                dp[w] = max(dp[w], dp[w - items[i][0]] + items[i][1]) +    print((dp[-1])) + + +solve2()