var m:array[0..100,0..100] of integer;
    v,w:array[1..100] of integer;
    i,j,k,n,b:integer;
    f,g:text;
begin
assign(f,'rucsac.in');reset(f);
assign(g,'rucsac.out');rewrite(g);
readln(f,n,b);
for i:=1 to n do
  readln(f,w[i],v[i]);

for i:=1 to b do
  m[0,i]:=0;

for i:=1 to n do
  for j:=0 to b do
    if j>=w[i] then
        if m[i-1,j]>m[i-1,j-w[i]]+v[i] then m[i,j]:=m[i-1,j]
          else m[i,j]:=m[i-1,j-w[i]]+v[i]
        else m[i,j]:=m[i-1,j];

for i:=0 to n do
  begin
    for j:=0 to b do
      write(g,m[i,j],'  ');
    writeln(g);
  end;


close(f);close(g);
end.