#include <fstream>
#include <iostream>

using namespace std;

int main() 
{
	ifstream fin ("energii.in");
	ofstream fout ("energii.out");
	
	long long i, j,g,w,b[1003],a[1003],v[5005],v1[5005];
	
	fin>>g>>w;
	for (i=0;i<g;i++)  
  		fin>>a[i]>>b[i];
  	for (i=0;i<=w;i++)
  		v[i] = v1[i] = -1;
  	
  	for (i=0;i<g;i++)
  	{
  		for(j=0;j<=w;j++)
  		{
  			if (a[i]<=j){
  				v[j] = b[i];
			}
			if (j-a[i]>=0)
  				if (v[j] <  b[i]+v1[j-a[i]])
  					v[j] = b[i]+v1[j-a[i]];
  		}
  		for(j=0;j<w;j++)
  			v1[j] = v[j];
  	}
  	
	fout<<v[w];
  	for (i=0;i<=w;i++)
		cout<<v[i]<<" ";	
	
	
	
	fin.close();
	fout.close();
	return 0;
}