#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int a[5001][10001],n,gr;

struct obiect
{
    int p,g;
}v[5001];

void citire()
{
    f>>n>>gr;
    int i;
    for(i=1;i<=n;i++)
    {
        f>>v[i].g>>v[i].p;
    }
}


void completare()
{
    int i,j;
    for(i=v[1].g;i<=gr;i++)
        a[1][i]=v[1].p;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=v[i].g;j++)
            a[i][j]=a[i-1][j];
        for(j=v[i].g+1;j<=gr;j++)
            a[i][j]=max(a[i-1][j],a[i-1][j-v[i].g]+v[i].p);
    }
}

int main()
{
    int i,j;
    citire();
    completare();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=gr;j++)
            g<<a[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}