program magica;
var n,pi,t,k,m,i,j,tot:longint;
    p,a,b:array[1..10000]of longint;
    f:array[0..10000]of longint;
    s,o:string;
begin
assign(input,'magica.in');
reset(input);
assign(output,'magica.out');
rewrite(output);
readln(n,pi);
for t:=1 to n do
  begin
    readln(s);
    for k:=1 to length(s) do
      if s[k]=' ' then break;
    if s[k]=' ' then
      begin
        o:=copy(s,1,k-1);
        s:=copy(s,k+1,length(s)-k);
        val(o,i,k);
        val(s,j,k);
        if j-i-pi>0 then
          begin
            inc(m);
            p[m]:=j-pi;
            a[m]:=i;
            b[m]:=j-i-pi;
          end
        else
          tot:=tot+i;
      end
    else
      begin
        val(s,i,k);
        tot:=tot+i;
      end;
  end;
if tot>=pi then
  begin
    for t:=1 to m do
      tot:=tot+p[t];
    writeln(tot);
    close(output);
    halt;
  end;
{for t:=1 to m-1 do
  for k:=1 to m-1 do
    if (p[k]>p[k+1])or(p[k]=p[k+1])and(a[k]<a[k+1]) then
      begin
        i:=p[k];p[k]:=p[k+1];p[k+1]:=i;
        i:=a[k];a[k]:=a[k+1];a[k+1]:=i;
      end;
for t:=1 to m do
  begin
    tot:=tot+a[t];
    if tot>=pi then break;
  end; }
j:=tot;
for i:=1 to m do
  tot:=tot+p[i];
for t:=1 to 10000 do f[t]:=1000000000;
for i:=1 to m do
  begin
    if (a[i]>=pi-j)and((b[i]<f[pi-j])or(f[pi-j]=1000000000))then f[pi-j]:=b[i];
    for k:=pi-j downto a[i] do
      if (f[k-a[i]]+b[i]<f[k])or(f[k]=0) then f[k]:=f[k-a[i]]+b[i];
  end;
tot:=tot-f[pi-j];
writeln(tot);
close(output);
end.