#include <fstream>

using namespace std;
ifstream cin("energii.in");
ofstream cout("energii.out");
struct ana{
int c;
int e;
}v[1002], car[150002];
int main()
{
    int n, w, i,j, smax;
    long long mini;
    smax=0;
    cin>>n>>w;
    for(i=1;i<=15000;i++)
        car[i].c=10000001;
    car[0].e=1;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].e>>v[i].c;
        for(j=smax;j>=0;j--)
            if(car[j].e==1)
            {
                car[j+v[i].e].e=1;
                if(car[j].c==10000001)
                    car[j+v[i].e].c=v[i].c;
                else
                    car[j+v[i].e].c=v[i].c+car[j].c;
            }
        smax+=v[i].e;
    }
    for(i=1;i<=smax;i++) cout<<i<<" "<<car[i].e<<" "<<car[i].c<<'\n';
    mini=10000001;
    for(i=1;i<=smax;i++)
        if(car[i].e==1&&i>=w) if(car[i].c<mini) mini=car[i].c;
    cout<<mini;
    return 0;
}