#include <fstream>

using namespace std;

ifstream intrare("rucsac.in");
ofstream iesire("rucsac.out");

int g[2000], c[2000], gmax;
int n, maxim, cmax[2000], ind;
int uz[2000][2000];

int main()
{
	int i, j, x, k;
	intrare >> n >> gmax;
	for(i = 0; i < n; i++)
		intrare >> g[i] >> c[i];
	for(j = 1; j <= gmax; j++)
	{
		maxim = -1;
		for(i = 0; i < n; i++)
			if (g[i] <= j && uz[j-g[i]][i] == 0)
			{
				x = c[i] + cmax[j-g[i]];
				if (x > maxim)
				{
					cmax[j] = x;
					maxim = x;
					for(k = 0; k < n; k++)
						uz[j][k]=uz[j-g[i]][k];
					uz[j][i] = 1;
				}
			}
	}
	
	maxim = -1;
	
	for(i = 1; i <= gmax; i++)
		if (cmax[i] > maxim)
			maxim = cmax[i];
		
	iesire << maxim << '\n';
	return 0;
}