#include <fstream>
#include <set>
#define inf 0x7fffffff
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int dp[5005];
set<int> s;
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    int n,w,minim=0x7fffffff;
    in>>n>>w;
    for(int i=0;i<=w;++i)
        dp[i]=inf;
    dp[0]=0;
    s.insert(0);
    for(int i=1;i<=n;++i)
    {
        int e,c;
        in>>e>>c;
        set<int>::iterator it=s.begin(),stop=s.end();
        do
        {
            --stop;
            int j=*stop;
            if(j+e<w)
                dp[j+e]=min(dp[j+e],dp[j]+c),s.insert(j+e);
            else if(j+e>=w)
                minim=min(minim,dp[j]+c);
        }while(it!=stop);
    }
    out<<minim;
    return 0;
}