#include <iostream>
#include <fstream>
using namespace std;

int N,G,p[20000],w[20000],s[20000];





int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>N;
    f>>G;
    int i,j;
    for (i=1;i<=N;i++)
    {
        f>>w[i]>>p[i];
    }
    for (i=1;i<=N;i++)
    {
        for (j=G;j>=w[i];j--)
        {
            if (s[j]<p[i]+s[j-w[i]])
            {
                s[j]=p[i]+s[j-w[i]];
            }
        }
        for (int k=1;k<=G;k++)
        cout<<s[k]<<" ";
        cout<<endl;
    }
    g<<s[G];
}