#include <cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
struct vm
{
    int cost;
    int pos;
};
struct fm
{
    int cost;
    bool pos;
};
int cmp(vm a,vm b)
{
    if(a.pos==b.pos)
    {
        if(a.cost<b.cost)
            return a.cost;
        else
            return b.cost;
    }
    else
        return a.pos<b.pos;
}
vm v[15005];
fm rucsac[15005];
int main()
{
    FILE *in,*out;
    in=fopen("energii.in","r");
    out=fopen("energii.out","w");
    int n,i,j,w,ras,ok;
    fscanf(in,"%d%d",&n,&w);
    for(i=1;i<=n;i++)
        fscanf(in,"%d%d",&v[i].pos,&v[i].cost);
    sort(v+1,v+n+1,cmp);
    rucsac[0].pos=true;
    for(i=1;i<=n;i++)
    {
        for(j=15000-v[i].pos;j>=0;j--)
        {
            if(rucsac[j].pos==1)
            {
                if(rucsac[j+v[i].pos].pos==0)
                {
                    rucsac[j+v[i].pos].pos=1;
                    rucsac[j+v[i].pos].cost=rucsac[j].cost+v[i].cost;
                }
                else
                {
                    if(rucsac[j+v[i].pos].cost<rucsac[j].cost+rucsac[v[i].cost].cost)
                        rucsac[j+v[i].pos].cost=rucsac[j].cost+rucsac[v[i].cost].cost;
                }

            }
        }
    }
    ok=0;
    ras=w;
    while(ok==0)
    {
        if(rucsac[ras].pos==1)
        {
            fprintf(out,"%d",rucsac[ras].cost);
            ok=1;
        }
        ras++;
    }
    return 0;
}