#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>castig;
vector<int>Gr,C;
vector<vector<bool> >Uz;
int main()
{
	FILE *in=fopen("rucsac.in","r");
	int n,g,i,j,s,k;
	fscanf(in,"%d %d",&n,&g);
	Gr.resize(n+1);
	C.resize(n+1);
	castig.resize(g+1,-1);
	Uz.resize(g+1);
	for(i=0;i<=n+1;++i) Uz[i].resize(n+1);
	for(i=1;i<=n;++i)
	{
		fscanf(in,"%d %d",&Gr[i],&C[i]);
	}
	fclose(in);
	castig[0]=0;
    for(s=1;s<=g;++s)
      for(i=1;i<=n;++i)
        if(Gr[i]<=s&&castig[s-Gr[i]]!=-1&&!Uz[s-Gr[i]][i])
          if(castig[s]<C[i]+castig[s-Gr[i]])
          {
              castig[s]=C[i]+castig[s-Gr[i]];
              for(k=1;k<=n;++k)
                Uz[s][k]=Uz[s-Gr[i]][k];
              Uz[s][i]=true;
          }
	FILE *out=fopen("rucsac.out","w");
	fprintf(out,"%d\n",*max_element(castig.begin(),castig.end()));
	fclose(out);
	return 0;
}