#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,a[50],c[50],b[50][50],d[50],p;
int main(){
	fin>>n>>g;
	for(int i=1; i<=n; i++) {fin>>a[i]>>c[i];
								b[i][0]=0;} 
	for(int i=1; i<a[1]; i++) b[1][i]=0;
	for(int i=a[1]; i<=g; i++) b[1][i]=c[1];
	for(int i=2; i<=n; i++){
		for(int j=1; j<=g; j++) if(j-a[i]<0) b[i][j]=b[i-1][j]; 
									else b[i][j]=max(b[i-1][j],b[i-1][j-a[i]]+c[i]);
	}
	
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=g; j++) fout<<setw(3)<<b[i][j]<<' ';
		fout<<'\n';
	}
	four<<b[n][g];
	/*fout<<"venitul max="<<b[n][g]<<'\n';
	fout<<"Pietrele:"<<'\n';
	int j=g;
	p=b[n][g];
	for(int i=n; i>1; i--){
		if(b[i-1][j]!=p){
			p-=c[i];
			while (b[i-1][j]!=p&&j>=1) j--;
			fout<<i<<":("<<a[i]<<";"<<c[i]<<")"<<'\n';
		}
		}
	if(p) fout<<"1:("<<a[1]<<";"<<c[1]<<")"<<'\n';
	/*for(int i=0; i<a[1]; i++) d[i]=0;
	for(int i=a[1]; i<=g; i++) d[i]=c[1];
	for(int i=2; i<=n; i++){
		for(int j=g; j>=0; j--) if(j+a[i]<=g) d[j+a[i]]=max(d[j+a[i]],d[j]+c[i]);
	}
	fout<<"v="<<d[g];*/
}