def main():

    N, W = [int(n) for n in input().split()]

    baggages = [[int(n) for n in input().split()] for i in range(N)]



    VALUE, WEIGHT = 1, 0

    dp = [[-1] * (W+1) for n in range(N)]

    # dp[baggage][weight] := baggage番目までの荷物を使ってweight以下に抑える

    dp[0] = [0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE] for weight in range(W+1)]



    for baggage in range(N):

        for max_weight in range(W+1):

            if dp[baggage][max_weight] != -1:

                continue

            bag_w = baggages[baggage][WEIGHT]

            bag_v = baggages[baggage][VALUE]

            val1 = dp[baggage-1][max_weight]

            val2 = dp[baggage-1][max_weight-bag_w]+bag_v if max_weight >= bag_w else 0

            dp[baggage][max_weight] = max(val1, val2)

            

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







if __name__ == "__main__":

    main()
N,W = [int(_n) for _n in input().split()]

A = []

for i in range(N):

    w,v = [int(_n) for _n in input().split()]

    A.append((w,v))

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



for w in range(W+1):

    dp[0][w] = 0 if w < A[0][0] else A[0][1]



for i in range(N):

    for w in range(W+1):

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

        if w >= A[i][0]:

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

print((dp[N-1][W]))
def main():
    N, W = [int(n) for n in input().split()]
    baggages = [[int(n) for n in input().split()] for i in range(N)]
    VALUE, WEIGHT = 1, 0
    dp = [[-1] * (W + 1) for n in range(N)]
    # dp[baggage][weight] := baggage番目までの荷物を使ってweight以下に抑える
    dp[0] = [
        0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE]
        for weight in range(W + 1)
    ]
    for baggage in range(N):
        for max_weight in range(W + 1):
            if dp[baggage][max_weight] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage - 1][max_weight]
            val2 = (
                dp[baggage - 1][max_weight - bag_w] + bag_v
                if max_weight >= bag_w
                else 0
            )
            dp[baggage][max_weight] = max(val1, val2)
    print((dp[N - 1][W]))


if __name__ == "__main__":
    main()

N, W = [int(_n) for _n in input().split()]
A = []
for i in range(N):
    w, v = [int(_n) for _n in input().split()]
    A.append((w, v))
dp = [[0] * (W + 1) for _ in range(N)]
for w in range(W + 1):
    dp[0][w] = 0 if w < A[0][0] else A[0][1]
for i in range(N):
    for w in range(W + 1):
        dp[i][w] = dp[i - 1][w]
        if w >= A[i][0]:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - A[i][0]] + A[i][1])
print((dp[N - 1][W]))

-def main(): -    N, W = [int(n) for n in input().split()] -    baggages = [[int(n) for n in input().split()] for i in range(N)] -    VALUE, WEIGHT = 1, 0 -    dp = [[-1] * (W + 1) for n in range(N)] -    # dp[baggage][weight] := baggage番目までの荷物を使ってweight以下に抑える -    dp[0] = [ -        0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE] -        for weight in range(W + 1) -    ] -    for baggage in range(N): -        for max_weight in range(W + 1): -            if dp[baggage][max_weight] != -1: -                continue -            bag_w = baggages[baggage][WEIGHT] -            bag_v = baggages[baggage][VALUE] -            val1 = dp[baggage - 1][max_weight] -            val2 = ( -                dp[baggage - 1][max_weight - bag_w] + bag_v -                if max_weight >= bag_w -                else 0 -            ) -            dp[baggage][max_weight] = max(val1, val2) -    print((dp[N - 1][W])) - - -if __name__ == "__main__": -    main() +N, W = [int(_n) for _n in input().split()] +A = [] +for i in range(N): +    w, v = [int(_n) for _n in input().split()] +    A.append((w, v)) +dp = [[0] * (W + 1) for _ in range(N)] +for w in range(W + 1): +    dp[0][w] = 0 if w < A[0][0] else A[0][1] +for i in range(N): +    for w in range(W + 1): +        dp[i][w] = dp[i - 1][w] +        if w >= A[i][0]: +            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - A[i][0]] + A[i][1]) +print((dp[N - 1][W]))