program rucsac;
   var p,w:array[0..10000] of longint;
   d,dc:array[0..10000] of longint;
   g,n,i,j,k:longint;
   var f,g1:text;
 function max(a,b:longint):longint;
    begin
     if a>b then exit(a);
     exit(b);end;

 begin
 assign(f,'rucsac.in');reset(f);
 assign(g1,'rucsac.out');rewrite(g1);
 readln(f,n,g);
    for i:=1 to n do readln(f,w[i],p[i]);
    for i:=1 to n do
          for j:=g downto w[i] do
          d[j]:=max(d[j],d[j-w[i]]+p[i]);
          writeln(g1,d[g]);
 close(g1);
 end.