#include <fstream>
#define inf 5000000
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
int i,j,n,W,v[5001],e,c;
int main()
{   f>>n;
    f>>W;
    for(i=1;i<=W;i++)
        v[i]=inf;
    for(i=1;i<=n;i++){
        f>>e>>c;
        for(j=W;j>=0;j--)
            if(v[j]!=inf){
                if(j+e<=W)
                    v[j+e]=min(v[j+e],v[j]+c);
                else
                    v[W]=min(v[W],v[j]+c);
            }
    }
    g<<v[W];
    return 0;
}