#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define max(a,b) ( a>b ? a : b)

unsigned N,G,P[5000],W[5000],i,j,matrice[10001][5001];


void rucsac( unsigned G,unsigned N,unsigned W[],unsigned P[])
    {
        for(i=0;i<=N;i++)
            matrice[i][0]=0;
        for(j=0;j<=G;j++)
            matrice[0][j]=0;

        for(i=1;i<=N;i++)
            for(j=1;j<=G;j++)
                if(W[i]<j)
                    matrice[i][j]=max(matrice[i-1][j],P[i]+matrice[i-1][j-W[i]]);
                else
                    matrice[i][j]=matrice[i-1][j];

        for(i=0;i<=N;i++)
            {for(j=0;j<=G;j++)
                fout<<matrice[i][j]<<" ";
                fout<<"\n";
            }
    }

int main()
    {
        fin>>N>>G;
        for(i=1;i<=N;i++)
            fin>>W[i]>>P[i];
        rucsac(G,N,W,P);

        return 0;
    }