var
  n,t,p,i,max,x,y,now:longint;
  b:array[0..10000,1..2]of longint;
  f:array[0..10000]of boolean;

procedure go(k,m:longint);
var
  i:longint;
begin
  if k=t+1 then
  begin
    if m>max then max:=m;
    exit;
  end;
  for i:=1 to t do
  if not f[i] then
  begin
    f[i]:=true;
    go(k+1,m+b[i,1]);
    f[i]:=false;
    if m>=p then
    begin
      f[i]:=true;
      go(k+1,m-p+b[i,2]);
      f[i]:=false;
    end;
  end;
end;

begin
  assign(input,'magica.in'); reset(input);
  assign(output,'magica.out'); rewrite(output);
  readln(n,p);
  for i:=1 to n do
  begin
    read(x);
    if not eoln then
    begin
      readln(y);
      if y-p>x then
      begin
        inc(t);
        b[t,1]:=x;
        b[t,2]:=y;
      end
      else inc(now,x);
    end
    else inc(now,x);
  end;
  max:=-maxlongint;
  go(1,now);
  writeln(max);
  close(input);
  close(output);
end.