with open("rucsac.in", "r", encoding="utf-8") as f:
	n, g = map(int, f.readline().split())

	objects = []

	for _ in range(n):
		w, p = map(int, f.readline().split())

		objects.append((w, p))

	dp = [[0] * (g + 1) for _ in range(n + 1)]

	for i, (w, p) in enumerate(objects):
		for j in range(1, g + 1):
			dp[i][j] = dp[i - 1][j]
			if j - w >= 0:
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + p)

	with open("rucsac.out", "w", encoding="utf-8") as out:
		out.write(str(dp[n - 1][g]))