#include<fstream>
#include<cstdio>
#include<climits>
#define MAX 99999999
using namespace std;
long n,m,w[1002],p[1002],d[5002][10002],mi,i,j;
int main()
{
    freopen("energii.in","r",stdin);
    ofstream g("energii.out");
scanf("%ld %ld",&n,&m);
mi=MAX;
for(i=1;i<=n;i++)
    scanf("%ld%ld",&w[i],&p[i]);
for(i=0;i<=m;i++)
    d[0][i]=MAX;
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
       {
           d[i][j]=d[i-1][j];
           if(j>w[i])
           {
               d[i][j]=min(d[i][j],d[i-1][j-w[i]]+p[i]);
           }
           else if(w[i]>=j)
            d[i][j]=min(d[i][j],p[i]);
       }
if(d[n][m]==MAX)
    g<<-1;
else
    g<<d[n][m];
g<<'\n';

for(i=1;i<=n;i++)
    {for(j=1;j<=m;j++)
        g<<d[i][j]<<" ";
    g<<'\n';
    }
return 0;
}