#include <fstream>

using namespace std;
struct nod{int w,c;};
ifstream f("energii.in");
ofstream g("energii.out");
int S,W,n,i,j;int a[5001];
int main()
{f>>n>>W;
nod v[n+1];

for(i=1;i<=n;i++)
    f>>v[i].w>>v[i].c;
 f.close();
a[0]=0;
  for(S=1;S<=W;S++) a[S]=-1;
 for(i=1;i<=n;i++)
     {

      for(S=1;S<=W;S++)


        if(a[S]!=-1 && a[S-v[i].w]!=-1 && S-v[i].w>=0)

            {if(a[S-v[i].w]+v[i].c<a[S])
                 a[S]=a[S-v[i].w]+v[i].c;}

            else

                a[S]=a[S-v[i].w]+v[i].c;

            g<<v[i].w<<' '<<v[i].c<<'\n';
            for(S=1;S<=W;S++)
                g<<a[S]<<' ';
            g<<'\n';
}


   g<<a[W];
   g.close();
}