#include<fstream>
#include<iostream>
#define MXN 5001
#define MXG 5001
using namespace std;
ifstream fin("rucsac.in" );
ofstream fout( "rucsac.out");
long V[MXG];
int n,g,k;
int w[MXN],p[MXN];
int rucsac()
{int i,j;
for (i=1;i<=n;i++)
{for(j=g;j>=w[i];j--)
V[j]=max(V[j],V[j-w[i]]+p[i]);
for(k=1;k<=g;k++) cout<<V[k]<<" ";
cout<<"\n";}
return V[g];}
int main()
{int i;
fin>>n>>g;
for (i=1;i<=n;i++) fin>>w[i]>>p[i];
fout<<rucsac();
return 0;}