#include<iostream>
#include<fstream>
#define MIN(a,b)((a)<(b) ? (a):(b))

using namespace std;

int main()
{
	ifstream cn("energii.in");
	ofstream co("energii.out");
	
	int nrg, w, eg[1001], cg[1001], a[1001][5001], i, j;
	cn>>nrg;
	cn>>w;
	
	for(i=1;i<=nrg;i++)
		cn>>eg[i]>>cg[i];
	
	for(i=1;i<nrg;i++)
	{
		for(j=1;j<=w;j++)
		{
			if(eg[i]<j)
				a[i][j]=a[i-1][j];
			else
				a[i][j]=MIN(a[i-1][j], cg[i]+a[i-1][j-eg[i]]);
			co<<a[i][j]<<" ";
		}
		co<<endl;
	}
	co<<a[nrg][w];
}