program energii;
   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 min(a,b:longint):longint;
    begin
     if a<b then exit(a);
     exit(b);end;

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