#include <bits/stdc++.h>

using namespace std;

int n,g,G[5010],P[5010],DP[2][5010];

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

int main(){
	cin>>n>>g;
	for(int i=0;i<n;i++){
		cin>>G[i]>>P[i];
	}
	memset(DP,0,sizeof DP);
	DP[0][G[0]]=P[0];
	for(int i=1;i<n;i++){
		memset(DP[i%2],0,sizeof DP[i%2]);
		for(int j=0;j<=g;j++){
			DP[i%2][j]=DP[(i-1)%2][j];
			if((j-G[i]>=0)&&DP[(i-1)%2][j-G[i]])DP[i%2][j]=max(DP[(i-1)%2][j-G[i]]+P[i],DP[i%2][j]);
			//if(j)DP[i%2][j]=max(DP[i%2][j-1],DP[i%2][j]);
			cout<<DP[i%2][j]<<' ';
		}
		cout<<'\n';
	}
	fout<<DP[(n-1)%2][g];
}