#include <iostream>
#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct ob
{
int p;
int gr;
};
ob v[5005];
int n,G,m[5000][10005];

int main ()
{
	int i,j;
	f>>n>>G;
	
	for(i=1;i<=n;i++)
		f>>v[i].gr>>v[i].p;
	
	for(i=1;i<=n;i++)
		for(j=0;j<=G;j++)
		{
			m[i][j]=m[i-1][j]; // nu se pune obiectul i
			if(v[i].gr<=j)
				m[i][j]=max(m[i][j], m[i-1][j-v[i].gr]+v[i].p); // incercam sa punem obiectul i pe o pozitie anterioara
		}
	for(i=1; i<=n; i++)
	{
		for(j=0; j<=G; j++)
		{
			g<<m[i][j]<<" ";
		}
		g<<"\n";
	}
	
}