#include <iostream>
#include <fstream>

using namespace std;
int e[1001],c[1002],dold[7000],dnew[7001];

int main()
{
    int g,w,j,i,wmax,maxx,minn;
    ifstream cmin("energii.in");
    ofstream cmout("energii.out");
    cmin>>g>>w;
    maxx=-100000;
    minn=100000;
    for(j=1;j<=g;++j){
        cmin>>e[j]>>c[j];
        if(c[j]>maxx){
            maxx=c[j];
        }
    }
    wmax=w+maxx;
    for(j=0;j<=wmax;++j){
        dold[j]=-1;
    }
    dold[0]=0;
    for(i=1;i<=g;++i){
        for(j=0;j<=wmax;++j){
            if(dold[j]==-1){
                dnew[j+e[i]]=dold[j+e[i]];
            }
            else if(dold[j+e[i]]==-1){
                dnew[j+e[i]]=dold[j]+c[i];
            }
            else{
                dnew[j+e[i]]=min(dold[j+e[i]],dold[j]+c[i]);
            }


        }
        for(j=0;j<=wmax;++j){
            dold[j]=dnew[j]; cout<<dold[j]<<" ";
        }
        cout<<endl;
    }
    for(j=w;j<=wmax;++j){

        if(dnew[j]<minn && dnew[j]!=-1){minn=dnew[j];}
    }
    cmout<<minn<<endl;


}