#include<iostream>
#include<fstream>
#define Nmax 5001
#define Gmax 10001

using namespace std;

int N,G,m[Gmax],g[Nmax],c[Nmax];

void citire_CreareMatrice() {
	ifstream f("rucsac.in");
	f >> N;
	f >> G;
	for(int i = 1; i <= N; i++) {
		f >> g[i];
		f >> c[i];
		for(int j = G ; j >= g[i]; j--) {
			if ( j >= g[i] ) {
				m[j] = max(m[j],m[j-g[i]] + c[i]);
			}
		}
		for (int j=0;j<=G;j++)
			cout<<m[j]<<"  ";
		cout<<endl;
	}
	f.close();
}


int main()
{
	citire_CreareMatrice();
	ofstream g("rucsac.out");
	g << m[G];
	g.close();
	return 0;
}