program magica;
var
  data:array [1..1000,1..2] of longint;
  p,p1,p2,i,nn,n,ans,m:longint;
procedure search(num,money:longint);
begin
  if num=nn+1 then begin
    if money>ans then ans:=money;
  end
  else begin
    if (money>=p) and (data[num,2]-p>data[num,1]) then search(num+1,money-p+data[num,2]);
    search(num+1,money+data[num,1]);
  end;
end;
begin
  assign (input,'magica.in');
  reset (input);
  readln (n,p);m:=0;nn:=0;
  for i:=1 to n do begin
    read (p1);
    if eoln(input) then m:=m+p1 else begin
          read (p2);
	  inc(nn);
	  data[nn,1]:=p1;
	  data[nn,2]:=p2;
          readln;
	end;
  end;
  close (input);
  assign (output,'magica.out');
  rewrite (output);
  ans:=0;
  search(1,m);
  writeln (ans);
  close (output);
end.