#include <iostream>
#include <fstream>
#define nmax 5005

using namespace std;



int n,w[10005],pmax,i,weight,j;
int a[5005][10005];
int p[5005];
ifstream f("rucsac.in");
ofstream g("rucsac.out");

/*void sub(int k){
    int i,cost,profit;
    if (k>n){
        cost=0;
        profit=0;
        for(i=1;i<=n;i++){
            if (v[i]==1) {
                cost=cost+per[i].first;
                profit=profit+per[i].second;
            }
            if (cost<=w && profit > pmax) pmax=profit;
        }
        return;
    }
    v[k]=1;
    sub(k+1);
    v[k]=0;
    sub(k+1);
}*/

int main()
{
    f >> n >> weight;
    for(j=1;j<=weight;j++) a[0][j]=-1;
    for(i=1;i<=n;i++){
        f >> w[i] >> p[i];
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=weight;j++){
            a[i][j]=a[i-1][j];
            if (j-w[i]>=0 && a[i-1][j-w[i]]!=-1)
            a[i][j]=max(a[i][j],a[i-1][j-w[i]]+p[i]);
        }
    }
    pmax=0;
    for(i=1;i<=weight;i++){
        if (a[n][i]>pmax) pmax=a[n][i];
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=weight;j++){
            cout << a[i][j] <<" ";
        }
        cout << "\n";
    }
    g << pmax;
}