/* Energii */
#include<fstream>
using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");

int n,w,i,j;
int m[3][5001];
int e[1001],c[1001];

int main()
{f>>n>>w;
for(i=1; i<=n; i++)
  f>>e[i]>>c[i];
for(i=1; i<=n; i++)
 {for(j=1; j<=w; j++)
   {if(j>e[i])
     {if((m[0][j]==0 || m[0][j]>m[0][j-e[i]]+c[i]) && m[0][j-e[i]]!=0)
        m[1][j]=m[0][j-e[i]]+c[i];
     else
        m[1][j]=m[0][j];} 
    else       
     {if(m[0][j]==0 || c[i]<m[0][j])
         m[1][j]=c[i];
      else
         m[1][j]=m[0][j];}  
    }
  for(j=1; j<=w; j++)
     m[0][j]=m[1][j];  
  } 
     
g<<m[1][w];               
return 0;}