#include<fstream>
using namespace std;
ifstream intrare("rucsac.in");
ofstream iesire("rucsac.out");
int g[1000],c[1000],uz[1000][1000],cmax[1000];
int n,gmax;
void citire()
{
	int i;
	intrare>>n>>gmax;
	for(i=1;i<=n;i++)
		intrare>>g[i]>>c[i];
}
void pd()
{
	int i,j;
	for(i=1;i<=gmax;i++)
	{
		for(j=i;j<=n;j++)
		{ 
			if(g[j]<=i && uz[i-g[j]][j]==0)
			{
				cmax[i]=i+cmax[i-g[j]];
				uz[i][j]=uz[i-g[j]][j];
				uz[j][i]=1;
			}
		}
	}				
}
void afisare()
{
	int i;
	int maxim;
	maxim=cmax[1];
	for(i=2;i<=gmax;i++)
		if(cmax[i]>maxim)
			maxim=cmax[i];
	iesire<<maxim<<'\n';	
}
int main()
{
	citire();
	pd();
	afisare();
	iesire.close();
	return 0;
}