#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int main()
{
    int n,Gmax,g[5005],v[5005],C[5005][10005],i,j;
    fi>>n>>Gmax;
    for(i=1;i<=n;i++){
        fi>>g[i]>>v[i];
    }
    for(i=0;i<=n;i++){
        C[i][0]=0;
    }
    for(j=0;j<=Gmax;j++){
        C[0][j]=0;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=Gmax;j++){
            if(g[i]>j||C[i-1][j-g[i]]+v[i]<C[i-1][j])
                C[i][j]=C[i-1][j];
            else
                C[i][j]=C[i-1][j-g[i]]+v[i];
        }
    }
    for(i=1;i<=n;i++){
            cout<<'\n';
        for(j=1;j<=Gmax;j++){
            cout<<C[i][j]<<" ";
        }
    }

}