#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,i,w[5010],p[5010],d[5010][10010],j;
int main()
{
   f>>n>>G;
   for(i=1;i<=n;i++)
   {
       f>>w[i]>>p[i];
   }
    for(i=1;i<=n;i++)
    for(j=0;j<=G;j++)
    {
        d[i][j]=d[i-1][j];
        if(w[i]<=j)
            d[i][j]=max(d[i][j] , d[i-1][j-w[i]] + p[i] ) ;
    }
    g<<d[n][G]<<' '<<endl;

    for(i=1;i<=n;i++)
    {
        for(j=0;j<=G;j++) g<<d[i][j]<<' ';g<<endl;
    }


}