ll@n,@m,d[m+1]{},e[],z=0;
rep(n){
	ll@a,@b,@c;
	c*=b;
	rep(i,a,m+1){
		e[i]=d[i-a]+c;
		if(i>=2a-b)e[i]>?=e[i-a+b]+c;
	}
	rep(i,a,m+1){
		d[i]>?=e[i];
	}
}
rep(p,1,m+1){
	z>?=d[p];
	wt(z);
}