#include <bits/stdc++.h>

using namespace std;

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

int N,G,W[100100],P[100100],DP[2][10100],L[10000][10000];
bool u=1;
int main(){
	cin >>N>>G;
	for (int i=1;i<=N;i++) cin >>W[i]>>P[i];
	
	for(int i=1;i<=N;i++){
		for (int j=1;j<=G;j++){
				if (W[i]<=j &&DP[!u][j]<DP[!u][j-W[i]]+P[i]){
					DP[u][j]=DP[!u][j-W[i]]+P[i];
					L[i][j]=1;
				}
				else {
					DP[u][j]=DP[!u][j];
				}

/*				if (W[i]<=j){
					DP[u][j]=max(DP[!u][j],DP[!u][j-W[i]]+P[i]);
				}
				else {
					
					DP[u][j]=DP[!u][j];
			
			
			}
	*/		
		cout <<DP[u][j]<<" ";
		}
		cout <<endl;
		u=!u;
	}
	cout <<DP[!u][G];

	//for (int i=1;i<=N;i++)
	//for (int j=1;j<=G;j++) fout <<DP[i][j]<<" \n"[j==G];
	return 0;
}