#include <stdio.h>

int main(void){
  int i,j,n,w;
  int slist[2][1001];
  int table[100][10000];

  scanf("%d %d",&n,&w);
  for(i=0;i<n;i++){
    scanf("%d %d",&slist[0][i],&slist[1][i]);
  }
  for(i=0;i<w;i++){
    if(slist[1][0]<=i)table[0][i]=slist[0][0];
  }
  for(i=0;i<n;i++){
    for(j=0;j<w;j++){
      if(j-slist[1][i]>0){
	if(table[i-1][j]>=table[i][j-slist[1][i]]+slist[0][i]){
	  table[i][j]=table[i-1][j];
	}
	else{
	  table[i][j]=table[i][j-slist[1][i]]+slist[0][i];
	}
      }

    }
  }
  printf("%d\n",table[n-1][w-1]);
  return 0;
}