program zzn;
type
        rec=record
        pp1,pp2:longint;
        end;
var
        i,j,n,p,total,p1,p2,num,ans:longint;
        data:array[1..1000]of rec;
        cha:array[1..1000]of longint;
        a,b:array[0..50]of integer;
procedure init;
        var
         st:integer;
         pp:array[1..2]of integer;
begin
        assign(input,'magica.in');
        reset(input);
        assign(output,'magica.out');
        rewrite(output);
        readln(n,p);
        total:=0;
        num:=0;
        for i:=1 to n do
        begin
            st:=0;
            fillchar(pp,sizeof(pp),0);
            while not eoln do
            begin
            inc(st);
            read(pp[st]);
            end;
            readln;
            p1:=pp[1];p2:=pp[2];
            if p2<p1 then
             begin
                 inc(total,p1);
             end else
             begin
                 if total>=p then
                  begin
                      inc(total,p2);
                      dec(total,p);
                  end else
                  begin
                      inc(num);
                      data[num].pp1:=p1;
                      data[num].pp2:=p2;
                  end;
             end;
        end;
end;
procedure closef;
begin
        close(input);
        close(output);
end;
procedure swap(var a,b:longint);
var
        t:longint;
begin
        t:=a;
        a:=b;
        b:=t;
end;
procedure swap2(var a,b:rec);
var
        t:rec;
begin
        t:=a;
        a:=b;
        b:=t;
end;
procedure dep(x,money:integer);
var
        i,s,pp:longint;
begin
        if x>num then
         begin
             if money>ans then ans:=money;
             exit;
         end;
        if money>=p then
         begin
             dep(x+1,money+data[x].pp2-p);
         end;
        dep(x+1,money+data[x].pp1);
end;
procedure main;
var
        l,r:longint;
begin
        ans:=0;
        if num=0 then
         begin
             writeln(total);
             exit;
         end;
        fillchar(a,sizeof(a),0);
        fillchar(b,sizeof(b),0);
        if n<=50 then
        begin
        dep(1,total);
        writeln(ans);
        end else
begin
        for i:=1 to num do cha[i]:=data[i].pp2-data[i].pp1;
        for i:=1 to num-1 do
         for j:=i+1 to num do
          if cha[i]>cha[j] then
           begin
              swap(cha[i],cha[j]);
              swap2(data[i],data[j]);
           end;
        l:=1;r:=num;
        while true do
        begin
           if total<p then
            begin
                inc(total,data[l].pp1);
                inc(l);
            end;
           while total>=p do
            begin
                inc(total,data[r].pp2);
                dec(r);
                dec(total);
            end;
           if l=r then
            begin
                if total>=p then inc(total,data[r].pp2) else inc(total,data[r].pp1);
            end;
        end;
end;
end;
begin
        init;
        main;
        closef;
end.