#include <bits/stdc++.h>
#define INFILE "energii.in"
#define OUTFILE "energii.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
const long long GMAX=1002;
const long long WMAX=5002;
long long G;
long long W;
array<array<long long,WMAX>,GMAX> C;
vector<long long> w;
vector<long long> c;
void Read(){
  in>>G>>W;
  w.resize(G+1);
  c.resize(G+1);
  for(long long i=1;i<=G;i++){
    long long a,b;
    in>>a>>b;
    w[i]=a;
    c[i]=b;
  }
}
void Determinare(){
  for(long long i=0;i<=G;i++){
    for(long long j=0;j<=W;j++){
      C[i][j]=INT_MAX;
    }
  }
  for(long long i=0;i<=G;i++)
    C[i][0]=0;
  for(long long i=1;i<=G;i++){
    for(long long e=0;e<=W;e++){
      if(w[i]>e)
        C[i][e]=C[i-1][e];
      else
        C[i][e]=min(C[i-1][e],C[i-1][e-w[i]]+c[i]);
    }
  }
  long long Min=INT_MAX;
  for(long long i=0;i<=G;i++){
    Min=min(Min,C[i][W]);
  }
  out<<Min;
}
int main(){
    Read();
    Determinare();
  return 0;
}