#include <fstream>

using namespace std;

int n, g, W[5010], P[5010];
int a[2][10010];

void Citire()
{
	ifstream f("rucsac.in");
	f>>n>>g;
	int i;
	for(i=1; i<=n; i++)
		f>>W[i]>>P[i];
	f.close(); 
}

void Rezolvare()
{
	int i, j;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=g; j++)
		{
			a[1][j] = a[0][j];
			if (W[i] <= j)
				a[1][j] = max(a[0][j], a[0][j-W[i]] + P[i]);
		}
		for(j=1; j<=g; j++)
			a[0][j] = a[1][j];
	}	

}

void Scriere()
{
	ofstream gout("rucsac.out");
	gout<<a[1][g]<<"\n";
	gout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Scriere();
	return 0;
}