#include <stdio.h>
#define DIM 1002
#define INF 10002

int v[DIM],c[DIM],s[5002];
int n,w,i,j,pMax,min;

  FILE *f = fopen("energii.in", "r");
  FILE *g = fopen("energii.out", "w");

int main(){

  fscanf(f,"%d %d",&n,&w);

  for (i=1; i<=n; i++)
    fscanf(f,"%d %d",&v[i],&c[i]);

  for (i=1; i<=5001; i++)
    s[i] = INF;

  pMax = 0;

  for (i=1; i<=n; i++)
    for (j=pMax; j>=0; j--) {
      if (s[j]!=INF) {
	if (j+v[i] > w) {
	  if (s[w] > s[j]+c[i])
	    s[w] = s[j]+c[i];
	}
	else {
	  if (s[j+v[i]] > s[j]+c[i])
	    s[j+v[i]] = s[j]+c[i];
	}
      }
      if (j+v[i] > pMax && j+v[i] <= w)
	pMax = j+v[i];
    }

  min = INF;

  for (i=1; i<=5001; i++)
    if (s[i] < min  && i >= w)
      min = s[i];

  fprintf(g,"%d",min);

  fclose(f);
  fclose(g);

  return 0;
}