#include<fstream>
#include<algorithm>
using namespace std;

int n,G,i,j,S,c[100002],minn;
struct gen
{
    int en,ct;
};
gen v[100002];

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

bool cmp(gen a,gen b)
{
    if(a.en<b.en) return 1;
    if(a.en==b.en && a.ct<b.ct) return 1;
    return 0;
}

int main()
{
    f>>n>>G;
    for(i=1;i<=n;i++)
    {
        f>>v[i].en>>v[i].ct;
        S+=v[i].en;
    }
    sort(v+1,v+n+1,cmp);

    c[0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=S-v[i].en;j>=0;j--)
        {
            if(c[j]!=0 && (c[j+v[i].en]==0 || (c[j+v[i].en]>c[j]+v[i].ct)))
            {
                c[j+v[i].en]=c[j]+v[i].ct;
            }
        }
    }

    minn=2000000000;
    for(i=G;i<=S;i++)
        if(c[i]-1<minn && c[i]!=0) minn=c[i]-1;

    g<<minn;

    f.close();
    g.close();
    return 0;
}