#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream out("rucsac.out");

const int NMax = 5e3 + 5;
int D[NMax][NMax];

int main()
{
    int val, x, G, n ;
    fin>>n>>G;
    for(int i = 1; i<=n ; i++)
    {


        fin>>x>>val;
        for(int j=1; j<=G; j++)
        {
            if(j>=x)
                D[i][j] = max(D[i-1][j], D[i-1][j-x] + val);
            else
                D[i][j] = D[i-1][j];
        }
    }


    for(int i= 1; i<=n ; i++)
    {

        for(int j=1; j<=G; j++)
            out<<D[i][j]<<" ";
        out<<"\n";
    }

    return 0;
}