Program ProbDisRuc;
type natural = 0..10000;
tab = array[natural,natural] of natural;
obj = record
 g,p:natural;
 end;
var a:array[natural] of obj;
b:tab;
i,j,n,w:natural;
f,g:text;
begin
assign(f,'rucsac.in');
assign(g,'rucsac.out');
reset(f);
rewrite(g);
readln(f,n,w);
for i:=1 to n do
 readln(f,a[i].g,a[i].p);
for i:=1 to n do begin
 for j:=1 to w do
 if j<a[i].g then
  b[i,j]:=b[i-1,j]
  else if b[i-1,j]<b[i-1,j-a[i].g]+a[i].p then begin
    b[i,j]:=b[i-1,j-a[i].g]+a[i].p;
   end else b[i,j]:=b[i-1,j]
end;
for i:=1 to n do begin
  for j:=1 to w do
   write(b[i,j],' ');
  writeln;
  end;
writeln(g,b[n,w]);
end.