#include<stdio.h>
#include<stdlib.h>
int main()
{
  int G,W,*cost,*energ,**mat,i,j;
  FILE *f=fopen("energii.in","r");
  FILE *g=fopen("energii.out","w");
  fscanf(f,"%d",&G);
  fscanf(f,"%d",&W);
  cost=(int *)malloc(G*sizeof(int));
  energ=(int *)malloc(W*sizeof(int));
  mat=(int **)malloc((G+1)*sizeof(int*));
  for(i=0;i<G;i++)
  {
                  mat[i]=(int *)malloc((W+1)*sizeof(int));
                  fscanf(f,"%d",&energ[i]);
                  fscanf(f,"%d",&cost[i]);
  }
  mat[G]=(int *)malloc((W+1)*sizeof(int));
  mat[0][0]=0;
  for(i=1;i<=W;i++)
    mat[0][i]=10001*1001;
  for(i=1;i<=G;i++)
    mat[i][0]=0;
  for(i=1;i<=G;i++)
     for(j=1;j<=W;j++)
      if(j-energ[i-1]>0)
         if( (mat[i-1][j-energ[i-1]]+cost[i-1])<mat[i-1][j])
             mat[i][j]=mat[i-1][j-energ[i-1]]+cost[i-1];
         else
             mat[i][j]=mat[i-1][j];
      else
          if(cost[i-1]<mat[i-1][j])
             mat[i][j]=cost[i-1];
          else
             mat[i][j]=mat[i-1][j];
  fprintf(g,"%d",mat[G][W]);
  fclose(f);
  fclose(g);
  return 0;
}