#include<fstream>

using namespace std;

short g,w,i,j,eg[1002],cg[1002],costmin[5004][5004];

short minim(short x,short y)
{
    if (x<y) return x;
        else return y;  
}
      

int main(void)
{  
    short min;
    ifstream fin("energii.in");
    ofstream fout("energii.out");
    fin >> g; fin >> w;
    for (i=1;i<=g;i++)
    {
        fin>>eg[i]; fin>>cg[i];
    }
      fin.close();
     for(i=1;i<=g;i++)
        for(j=1;j<=w;j++)
        {
            min=costmin[i-1][j];
            if(min==0)
                if(eg[i]+eg[i-1]>=j) min=costmin[i-1][j-eg[i]]+cg[i];
                 else ;
            else min=minim(min,costmin[i-1][j-eg[i]]+cg[i]);     
                                                         
           costmin[i][j]=min; 
        }  
   /*  for (i=1;i<=g;i++){
       for(j=1;j<=w;j++)
         fout<<costmin[i][j]<< "     ";
         fout<<"\n";        
         }*/
         fout<<costmin[g][w];
         
     fout.close(); 
}