#include <bits/stdc++.h>
using namespace std;

#define e '\n'

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

struct dub
{
	int gr, p;
} V[100];

int i,j,n,G, lc, lp, dp[2][1000];

int main()
{
	in >> n >> G;
	for(i=1; i<=n; i++)
	in >> V[i].gr >> V[i].p;
	
	lc=1, lp=0;
	for(i=1; i<=n; i++, lc^=1, lp^=1)
	for(j=1; j<=G; j++) 
	{
		if(V[i].gr<=j) 
		dp[lc][j]=max(dp[lp][j-V[i].gr]+V[i].p,dp[lp][j]);
		else dp[lc][j]=dp[lp][j];
		
		for(int a=0; a<=1; a++)
        {
        	for(int b=1; b<=G; b++)
        	out << " " << dp[a][b];
        	out << e;
		}
		out << e;
		
	}
	out << " " << dp[lp][G];


return 0;
}