#include<vector>
#include<stdio.h>

FILE *fin = fopen("rucsac.in","r");
FILE *fout = fopen("rucsac.out","w");

using namespace std;
vector< vector <int> > a;
vector<int>b;
vector<int>c;
vector<int>g;
vector<int>cMax;
int n,gMax,i,x;

int main()
{
	fscanf(fin,"%d%d",&n,&gMax);
	for(i=0;i<=n;i++)
		b.push_back(0);
	for(i=0;i<=gMax;i++)
		a.push_back(b);
	
	c.push_back(0);
	g.push_back(0);
	cMax.push_back(0);
	for(i=1;i<=n;i++)
	{
		fscanf(fin,"%d",&x);
		g.push_back(x);
		fscanf(fin,"%d",&x);
		c.push_back(x);
		cMax.push_back(-1);
	}
	
	for(i=n;i<=gMax;i++);
		cMax.push_back(-1);
	
	for(int S=1;S<=gMax;S++)
	{
		for(i=1;i<=n;i++)
			if(g[i]<=S && !a[S-g[i]][i] && cMax[S-g[i]]!=-1)
				if(cMax[S]<c[i]+cMax[S-g[i]])
				{
					cMax[S] = c[i]+cMax[S-g[i]];
					for(int k=1;k<=n;k++)
						a[S][k] = a[S-g[i]][k];
					a[S][i]=1;
				}
	}
	
	fprintf(fout,"%d",cMax[gMax]);
}