var n,g,i,j,gg:longint;
     w,p:array[1..5001] of longint;
     dp:array[0..10001] of longint;


begin
assign(input,'rucsac.in');
assign(output,'rucsac.out');
reset(input);
rewrite(output);

   read(n); readln(g);

     for i:=1 to n do
      begin
       read(w[i]); readln(p[i]);
      end;

      for i:=1 to n do
       for j:=g-w[i] downto 0 do
        if dp[j+w[i]]<dp[j]+p[i] then begin
                                       dp[j+w[i]]:=dp[j]+p[i];
                                       if gg<dp[j+w[i]] then gg:=dp[j+w[i]];
                                      end;

          for i:=1 to g do
           write(dp[i],' ');
         writeln(gg);

close(input);
close(output);
{Si totusi este trist in lume.}
end.