#include <stdio.h>
long v[10001];
int g[5001], p[5001];
int main () {
  FILE *fin, *fout;
  fin=fopen("rucsac.in", "r");
  fout=fopen("rucsac.out", "w");
  int n, G, i, j;
  fscanf(fin,"%d%d", &n, &G);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d%d", &g[i], &p[i]);
  for(i=1;i<=n;i++)
   for(j=G;j>=g[i];j--) {
     if(v[j]>v[j-g[i]]+p[i] )
       v[j]=v[j];
     else
       v[j]=v[j-g[i]]+p[i];
   }
  fprintf(fout,"%d", v[G]);
  fclose(fin);
  fclose(fout);
  return 0;
}