#include<fstream.h>
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,w[5005],p[5005],d[2][10005];
int main()
{ int i,j;
  f>>n>>G;
  for(i=1;i<=n;++i) f>>w[i]>>p[i];
  d[0][w[1]]=p[1];
  for(i=2;i<=n;++i)
	  { for(j=1;j<=w[i];++j) d[1][j]=d[0][j];
	    for(;j<=G;++j) if(d[0][j] > d[0][j-w[i]]+p[i]) d[1][j]=d[0][j];
							else if(d[0][j-w[i]]>0) d[1][j]=d[0][j-w[i]] + p[i];
									else if(j!=w[i])d[1][j]=d[0][j];
											else d[1][j]=p[i];
		for(j=1;j<=G;++j) d[0][j]=d[1][j];
	  }
  g<<d[0][G]<<'\n';
  f.close(); g.close();
  return 0;
}