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