#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, g, w[5005], p[5005], dp[2][100005];

int main()
{
	int i, j, ind = 1, sol = 0;
	fin >> n >> g;
	for (i = 1; i <= n; i++)
		fin >> w[i] >> p[i];

	for (i = 1; i <= n; i++, ind ^= 1)
		for (j = g; j >= 0; j--)
			if (j >= w[i])
				dp[ind][j] = max(dp[ind ^ 1][j], dp[ind ^ 1][j - w[i]] + p[i]);
			else dp[ind][j] = dp[ind ^ 1][j];

	for (i = 0; i <= g; i++)
		sol = max(sol, dp[ind ^ 1][i]);
	fout << sol << "\n";

	return 0;
}