program magica;
var i,j,m,n,p,v,s,x:longint;
  A,B:array[1..1000]of longint;
function Pack:longint;
var F:array[0..5000]of longint;
begin
  F[0]:=0;
  for i:=1 to p do F[i]:=MAXLONGINT shr 2;
  for i:=1 to m do
    for j:=p downto 0 do
    begin
      s:=j+A[i];
      if s>p then s:=p;
      if F[s]>F[j]+B[i]-p-A[i] then F[s]:=F[j]+B[i]-p-A[i];
    end;
  exit(x-F[p]);
end;
begin
  assign(input,'magica.in'); reset(input);
  assign(output,'magica.out'); rewrite(output);
  readln(n,p);
  m:=0; x:=0; v:=0;
  for i:=1 to n do
  begin
    m+=1;
    read(A[m]);
    v+=A[m];
    if not eoln
      then begin
        readln(B[m]);
        if B[m]-A[m]-p>0
          then x+=(B[m]-p)
          else begin B[m]:=p+A[m]; x+=A[m]; end;
      end
      else begin B[m]:=p+A[m]; x+=A[m]; end;
  end;
  if v<p then writeln(v) else writeln(Pack);
  close(input); close(output);
end.