#include<fstream>
#include<iostream>
using namespace std;
int n,g,w[100],p[100],a[100][100];

int main()
{
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	in>>n>>g;
	for(int i=1;i<=n;i++)
	{
		in>>w[i]>>p[i];
	}
	in.close();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=g;j++)
		{
			if(j-w[i] >= 0)
			{
				a[i][j]=max(a[i-1][j], a[i-1][j-w[i]]+p[i]);
			}
			else
				a[i][j]=a[i-1][j];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=g;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<"\n";
	}
	
	cout<<a[n][g];
	return 0;
}