var i,k,n,cs,gr,cas,g:integer;
         st,c,ge:array[1..100] of integer;
         as,ev:boolean;
         f:text;
         procedure init;
         begin
         st[k]:=-1;
         end;
                procedure succesor;
                begin
                as:=false;
                if st[k]<1 then begin
                st[k]:=st[k]+1;
                as:=true;
                end;
                end;
         procedure valid;
         begin
         g:=0;
         for i:=1 to k do
          g:=g+st[i]*ge[i];
          if g<=gr then ev:=true else ev:=false;
         end;
                function solutie:boolean;
                begin
               solutie:=(k=n);
                end;
         procedure calc;
         begin
         cas:=0;
         for i:=1 to k do
         cas:=cas+c[i]*st[i];
         if cas>cs then cs:=cas;
         end;
     begin
        assign(f,'rucsac.in');
     reset(f);
     read(f,n,gr);
     readln(f);
     for i:=1 to n do  begin
     read(f,ge[i],c[i]);
     readln(f);
     end;
      k:=1;
  init;
  while k>0 do begin
  repeat
  succesor;
  if as then valid
  until (not as) or (as and ev);
  if as then
  if solutie then calc
  else begin
  k:=k+1;
  init;
  end
  else k:=k-1;
  end;
  assign(f,'rucsac.out');
  rewrite(f);
  write(f,cs);
  close(f);
  end.