#include <fstream>
using namespace std;
ifstream intrare("rucsac.in");
ofstream iesire("rucsac.out");

int cmax[500], uz[500][500], N, g[500], c[500], GMAX;

void citire();
void afisare();
void pd();

int main()
	{
	citire();
	pd();
	afisare();
	return 0;
	}

void citire()
	{
	int i;
	intrare>>N>>GMAX;
	for (i=1;i<=N;i++)intrare>>g[i]>>c[i];
	}

void pd()
	{
	int G, maxi, i, j, pozi=0;
	for (G=0;G<=GMAX;G++)
		{
		maxi=-999999;
		for (i=1;i<=N;i++)
			if (c[i]+cmax[G-g[i]]>maxi && g[i]<=G && uz[G-g[i]][i]==0)
				{
				maxi=c[i]+cmax[G-g[i]];
				cmax[G]=maxi;
				for (j=1;j<=N;j++)
					if (j!=i)
						uz[G][j]=uz[G-g[i]][j];
				uz[G][i]=1;
				}
		}
	}

void afisare()
	{
	int maxi=-999999, G;
	for (G=1;G<=GMAX;G++)
		if (cmax[G]>maxi)
			maxi=cmax[G];
	iesire<<maxi;
	}