#include <stdio.h>
FILE *f,*g;
long n,w,i,j,max,a[1001],b[1001],maxn=20001;
long c[20001],d[20001];
int main(){
 f=fopen("energii.in","r");
 g=fopen("energii.out","w");
 fscanf(f,"%ld",&n);
 fscanf(f,"%ld",&w);
 for(i=1;i<=n;i++)
  fscanf(f,"%ld%ld",&a[i],&b[i]);
 max=0;
 for (i=0;i<=maxn;i++){ c[i]=-1;d[i]=-1;}
 c[0]=0;d[0]=0;
 for (i=1;i<=n;i++)
  for (j=max;j>=0;j--)
   if (c[j]!=-1)
    if (c[j+a[i]]==-1){
     c[j+a[i]]=a[i];
     d[j+a[i]]=b[i]+d[j];
     if (max<j+a[i]) max=j+a[i];
    }
     else
      if (d[j+a[i]]>d[j]+b[i]){
       c[j+a[i]]=a[i];
       d[j+a[i]]=b[i]+d[j];
       if (max<j+a[i]) max=j+a[i];
      }
 while (c[w]==-1) w++;
 fprintf(g,"%ld\n",d[w]);
 fclose(f);
 fclose(g);
 return 0;
}