#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N,G,i,j;
int p[3000],g[3000];
int dp[3000][3000];
int main()
{
    fin>>N>>G;
    for(i=1;i<=N;i++)
    {
        fin>>g[i]>>p[i];
    }
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=G;j++)
        {
            dp[i][j]=-1;
        }
    }
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=G;j++)
        {
            if(dp[i-1][j-g[i]]!=-1 && j-g[i]>=0)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-g[i]]+p[i]);
            }
            else
                dp[i][j]=dp[i-1][j];


        }

    }
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=G;j++)
            fout<<dp[i][j]<<" ";
        fout<<endl;
    }


}