program orase;
var f,g:text;
        m,n:longint;
        v,d:array[1..50001] of longint;



procedure iofile;
var i:longint;
begin
        assign(f,'orase.in');
        reset(f);
        assign(g,'orase.out');
        rewrite(g);
        readln(f,m,n);
        for i:=1 to n do
                readln(f,d[i],v[i]);
        close(f);
end;



procedure pozitie(var m:longint;p,u:longint);
var i,j,di,dj,aux:longint;
begin
        i:=p;
        j:=u;
        di:=0;
        dj:=-1;
        while i<j do
                begin
                        if d[i]>d[j] then
                                begin
                                        aux:=di;
                                        di:=-dj;
                                        dj:=-aux;
                                        aux:=v[i];
                                        v[i]:=v[j];
                                        v[j]:=aux;
                                        aux:=d[i];
                                        d[i]:=d[j];
                                        d[j]:=aux;
                                end;
                        i:=i+di;
                        j:=j+dj;
                end;
        m:=i;
end;



procedure quick(p,u:longint);
var m:longint;
begin
        if p<u then
                begin
                        pozitie(m,p,u);
                        quick(p,m-1);
                        quick(m+1,u);
                end;
end;

function dist(i,j:longint):longint;
begin
        dist:=v[i]+v[j]+abs(d[i]-d[j]);
end;

procedure solve;
var i,dm,x,y,xx,yy:longint;
begin
        quick(1,n);
        dm:=v[1]+v[2]+abs(d[2]-d[1]);
        x:=1;
        y:=2;
        for i:=3 to n do
                begin
                        xx:=x;
                        yy:=y;
                        if dist(xx,yy)<dist(x,i) then
                                begin
                                        xx:=x;
                                        yy:=i;
                                end;
                        if dist(xx,yy)<dist(y,i) then
                                begin
                                        xx:=y;
                                        yy:=i;
                                end;
                        x:=xx;
                        y:=yy;
                        dm:=dist(xx,yy);
                end;
        writeln(g,dm);
        close(g);
end;

begin
        iofile;
        solve;
end.