program problema_rucsacului;
var i,j,N,G:integer; L1,L2:array[0..10005] of longint;
W,P:array[1..5005] of longint; fin,fout:text;
bufin:array[0..50000] of byte;
begin
Assign(fin,'rucsac.in'); Reset(fin);
settextbuf(fin,bufin);
Readln(fin,N,G);
For i:=1 to N do
 Readln(fin,W[i],P[i]);
Writeln('==========================================');
For i:=1 to N do
 begin
 L2[j]:=L1[j];
 For j:=1 to G do
  begin
  If j<W[i] then continue;

  If L2[j]<L1[j-W[i]]+P[i] then
   L2[j]:=L1[j-W[i]]+P[i];
  end;
 For j:=0 to G do L1[j]:=L2[j];
 For j:=1 to G do Write(L1[j],' ');
 Writeln;
 end;

Assign(fout,'rucsac.out'); Rewrite(fout);
Write(fout,L2[G]);
Close(fout);
end.