#include <iostream>
#include <fstream>

#define in short int
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
in n,m,a[5001],b[5001],c[10001],d[10001];
void citire()
{
    f>>n>>m;
    for(int i=1;i<=n;i++){
        f>>a[i]>>b[i];
    }
    a[n+1]=b[n+1]=0;
}
void afisare()
{
    for(int i=1;i<=m;i++)cout<<d[i]<<" ";
    cout<<endl;
}
void dinamica ()
{
    d[a[1]]=b[1];
    afisare();
    for(in  i=2;i<=n;i++){
        for(in j=1;j<=m;j++)c[j]=d[j];
        if(d[a[i]]<b[i])d[a[i]]=b[i];
        for(in j=a[i];j<=m;j++){
            if(d[j]<(c[j-a[i]]+b[i])&&c[j-a[i]]!=0){
                d[j]=c[j-a[i]]+b[i];
            }
        }
        afisare();
    }
    g<<d[m];
}

int main()
{
    citire();
    dinamica();
    return 0;
}