#include <fstream>
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
#define inf 999999
int i,j,x,y,n,w,b[5002];
int main()
{ f>>n>>w;
  for(i=1;i<=w;++i)
    b[i]=inf;
    b[0]=0;
  for(i=1;i<=n;++i)
  {f>>x>>y;
   if(x>w)
   {if(b[w]>y||b[w]==0)
     b[w]=y;

   }
   else
   {
       for(j=w-x;j>=0;--j)
        if(b[j+x]>b[j]+y)
          b[j+x]=b[j]+y;
       for(j=0;j<=x;++j)
         if(b[j]>y)
         b[j]=x;
   }

  }
    g<<b[w]<<'\n';
    return 0;
}