program magica;
var
  s:string;
  i,j,n,p,m,ans,min,temp,m2:longint;
  code:integer;
  sz,sz2:array[1..5000,1..2]of longint;
  b:array[1..5000]of longint;
begin
  assign(input,'magica.in');
  assign(output,'magica.out');
  reset(input);
  rewrite(output);
  readln(n,p);
  for i:=1 to n do
  begin
    readln(s);
    if pos(' ',s)=0 then begin
      val(s,sz[i,1],code);
      sz[i,2]:=sz[i,1];
    end
    else begin
      val(copy(s,1,pos(' ',s)-1),sz[i,1],code);
      val(copy(s,pos(' ',s)+1,length(s)-pos(' ',s)),sz[i,2],code);
    end;
  end;
  m:=0;
  ans:=0;
  for i:=1 to n do
  begin
    if sz[i,2]-sz[i,1]>p then begin
      m:=m+1;
      sz2[m]:=sz[i];
    end
    else ans:=ans+sz[i,1];
  end;
  m2:=0;
  min:=0;
  if ans<p then begin
    temp:=p-ans;
    min:=2000000000;
    for i:=1 to p do
      b[i]:=2000000000;
    for i:=1 to m do
    begin
      for j:=temp-1 downto 1 do
        if j+sz2[i,1]>=temp then begin
          if b[j]+sz2[i,2]-sz2[i,1]<min then begin
            min:=b[j]+sz2[i,2]-sz2[i,1]+p;
            m2:=j+sz2[i,1];
          end;
        end
        else begin
          if b[j]+sz2[i,2]-sz2[i,1]<b[j+sz2[i,1]] then begin
            b[j+sz2[i,1]]:=b[j]+sz2[i,2]-sz2[i,1]+p;
          end;
        end;
      if sz2[i,1]>=temp then begin
        if sz2[i,2]-sz2[i,1]<min then begin
          min:=sz2[i,2]-sz2[i,1]+p;
          m2:=sz2[i,1];
        end;
      end
      else begin
        if b[sz2[i,1]]>sz2[i,2]-sz2[i,1] then b[sz2[i,1]]:=sz2[i,2]-sz2[i,1];
      end;
    end;
  end;
  ans:=ans+m2;
  for i:=1 to m do
    ans:=ans+sz2[i,2]-p;
  ans:=ans-min;
  writeln(ans);
  close(input);
  close(output);
end.