#include <cstdio>
#include <iostream>

using namespace std;

int C[1002][5002],eg[1002],cg[1002],i,j,n,w;

int main()
{
    FILE *f,*g;
    f=fopen("energii.in","r");
    g=fopen("energii.out","w");
    fscanf(f,"%d%d",&n,&w);
    for (i=1; i<=n; i++) fscanf(f,"%d%d",&eg[i],&cg[i]);
   // for (i=0; i<=n; i++) C[i][0]=10001;
   // for (i=1; i<=w; i++) C[0][i]=10001;
    for(i=1; i<=n; i++)
      for(j=1; j<=w; j++)
          if (eg[i]<j) C[i][j]=C[i-1][j];
          else
             if (C[i-1][j]!=0) C[i][j]=min(cg[i]+C[i-1][j-eg[i]],C[i-1][j]);
             else C[i][j]=cg[i]+C[i-1][j-eg[i]];
    fprintf(g,"%d\n",C[n][w]);
    for(i=1; i<=n; i++)
    {
     for(j=1; j<=w; j++) fprintf(g,"%d ",C[i][j]);
     fprintf(g,"\n");
    }
    return 0;
}