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

//dp[N][W] - profitul maxim pt o submultime a primelor N elemente ce are greutatea maxim W
//dp[N][W] = max(dp[N-1][W],dp[N-1][W-w[N]]+w[N])

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

int main() {
	int n, g;
	cin >> n >> g;
	int w[n+1], p[n+1], dp[n+1][g+1];
	for(int i=1;i<=n;i++) 
		cin >> w[i] >> p[i];
	for(int i=0;i<=g;i++)
		dp[0][i] = 0;
	for(int i=1;i<=n;i++) {
		dp[i][0] = 0;
		for(int j=1;j<=g;j++) {
			dp[i][j] = dp[i-1][j];
			if(j>=w[i])
				dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+p[i]); 
		}
	}
	for(int i=0;i<=n;i++) {
		for(int j=0;j<=g;j++)
			cout << dp[i][j] <<' ';
		cout << '\n';
	}
	return 0;
}