#include<fstream>
using namespace std;

const int MAXN=10005;

int w[MAXN>>1],p[MAXN>>1],sol[MAXN];	//,m[MAXN][MAXN];
int n,g,optim;

void citire()
{
	int i;
	ifstream fin("rucsac.in");
	fin>>n>>g;
	for (i=1;i<=n;i++)
		fin>>w[i]>>p[i];
	fin.close();
}

void rezolva()
{
	int i,j;
	/*	cu matrice
	int i,j;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=g;j++)
		{
			m[i][j]=m[i-1][j];
			if (j>=w[i] && m[i][j]<m[i-1][j-w[i]]+p[i])
				m[i][j]=m[i-1][j-w[i]]+p[i];
		}
	}
	*/
	for (i=1;i<=n;i++)
	{
		for (j=g;j>=0;j--)
		{
			if (j>=w[i] && sol[j]<sol[j-w[i]]+p[i])
				sol[j]=sol[j-w[i]]+p[i];
		}
	}
}
void afisare()
{
	int j;
	ofstream fout("rucsac.out");
	for (j=1;j<=g;j++)
		if (sol[j]>optim)
			optim=sol[j];
	fout<<optim<<'\n';
	fout.close();
}
int main()
{
	citire();
	rezolva();
	afisare();
	return 0;
}