import sys

# import numpy as np

inp = sys.stdin.readline

read = lambda: list(map(int, inp().strip().split()))

# import profile



def solve():

	n, w = read(); 

	dp = [[0 for i in range(w+1)] for j in range(n)]

	w_v_list = [read() for i in range(n)]

	# for i in dp:print(*i)

	# print("\n")

	# print(w_v_list)

	for i in range(n):

		for j in range(w+1):

			elem_w, elem_v = w_v_list[i]

			if elem_w <= j:

				dp[i][j] = max(elem_v + dp[i-1][j - elem_w], dp[i][j-1], dp[i-1][j])

				# w_v_list[i][1] = 0

			else:

				dp[i][j] = max(dp[i][j-1], dp[i-1][j])

	# for i in dp:print(*i)

	print((dp[n-1][w]))









if __name__ == "__main__":

	solve()
import sys

# import numpy as np

inp = sys.stdin.readline

read = lambda: list(map(int, inp().strip().split()))

# import profile



def solve():

	n, w = read(); 

	dp = [[0 for i in range(w+1)] for j in range(3)]

	w_v_list = [read() for i in range(n)]

	# for i in dp:print(*i)

	# print("\n")

	# print(w_v_list)

	for i in range(n):

		for j in range(w+1):

			elem_w, elem_v = w_v_list[i]

			if elem_w <= j:

				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])

				# w_v_list[i][1] = 0

			else:

				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])

		dp[(i+1)%3] = [0]*(w+1)

		# for i in dp:print(*i)

		# print("\n")

	print((dp[(n-1)%3][w]))









if __name__ == "__main__":

	solve()
import sys

# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile
def solve():
    n, w = read()
    dp = [[0 for i in range(w + 1)] for j in range(n)]
    w_v_list = [read() for i in range(n)]
    # for i in dp:print(*i)
    # print("\n")
    # print(w_v_list)
    for i in range(n):
        for j in range(w + 1):
            elem_w, elem_v = w_v_list[i]
            if elem_w <= j:
                dp[i][j] = max(
                    elem_v + dp[i - 1][j - elem_w], dp[i][j - 1], dp[i - 1][j]
                )
                # w_v_list[i][1] = 0
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    # for i in dp:print(*i)
    print((dp[n - 1][w]))


if __name__ == "__main__":
    solve()

import sys

# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile
def solve():
    n, w = read()
    dp = [[0 for i in range(w + 1)] for j in range(3)]
    w_v_list = [read() for i in range(n)]
    # for i in dp:print(*i)
    # print("\n")
    # print(w_v_list)
    for i in range(n):
        for j in range(w + 1):
            elem_w, elem_v = w_v_list[i]
            if elem_w <= j:
                dp[i % 3][j] = max(
                    elem_v + dp[(i - 1) % 3][j - elem_w],
                    dp[i % 3][j - 1],
                    dp[(i - 1) % 3][j],
                )
                # w_v_list[i][1] = 0
            else:
                dp[i % 3][j] = max(dp[i % 3][j - 1], dp[(i - 1) % 3][j])
        dp[(i + 1) % 3] = [0] * (w + 1)
        # for i in dp:print(*i)
        # print("\n")
    print((dp[(n - 1) % 3][w]))


if __name__ == "__main__":
    solve()

-    dp = [[0 for i in range(w + 1)] for j in range(n)] +    dp = [[0 for i in range(w + 1)] for j in range(3)] -                dp[i][j] = max( -                    elem_v + dp[i - 1][j - elem_w], dp[i][j - 1], dp[i - 1][j] +                dp[i % 3][j] = max( +                    elem_v + dp[(i - 1) % 3][j - elem_w], +                    dp[i % 3][j - 1], +                    dp[(i - 1) % 3][j], -                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) -    # for i in dp:print(*i) -    print((dp[n - 1][w])) +                dp[i % 3][j] = max(dp[i % 3][j - 1], dp[(i - 1) % 3][j]) +        dp[(i + 1) % 3] = [0] * (w + 1) +        # for i in dp:print(*i) +        # print("\n") +    print((dp[(n - 1) % 3][w]))