#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cstring>
using namespace std;
ifstream in("orase.in");
ofstream out("orase.out");
int first_real,last_real;
struct leg{
    int dist,length;
    bool operator<(const leg& other) const {
        return dist<other.dist;
    }
};
struct ed{
    int nod,length;
};
ed edge;
leg el;
set<int> multime;
const int NMAX=100011;
const int OFFSET=50003;
int n,m,d,l;
int dij[NMAX];
vector<ed> adj[NMAX];
map<int,int> d_to_ind;
vector<leg> vec;
struct node{
    int ind,dist;
    bool operator<(const node& other)const{
        return dist<other.dist;
    }
};
node aux;
priority_queue<node> pq;
int farnode(int nod)
{
    memset(dij,20000007,sizeof(dij));
    aux.ind=nod;
    aux.dist=0;
    pq.push(aux);
    dij[aux.ind]=0;
    while(!pq.empty())
    {
        node varf=pq.top();
        pq.pop();
        if(dij[varf.ind]==varf.dist)
        {
            for(auto w:adj[varf.ind])
            {
                if(varf.dist+w.length<dij[w.nod])
                {
                    aux.ind=w.nod;
                    aux.dist=varf.dist+w.length;
                    dij[aux.ind]=min(dij[aux.ind],varf.dist+w.length);
                    pq.push(aux);
                }
            }
        }
    }
    int maxx=-1;
    int far;
    for(int i=first_real;i<=last_real;i++)
    {
        if(dij[i]>maxx)
        {
            maxx=dij[i];
            far=i;
        }
    }
    return far;
}
int main()
{
    in>>m>>n;
    for(int i=1;i<=n;i++)
    {
        in>>el.dist>>el.length;
        multime.insert(el.dist);
        vec.push_back(el);
    }
    int ct=0;
    int prev_dist=0;
    for(auto it=multime.begin();it!=multime.end();++it)
    {
        ct++;
        d_to_ind[*it]=ct;
        if(ct>=2)
        {
            edge.nod=ct;
            edge.length=(*it)-prev_dist;
            adj[ct-1].push_back(edge);
            edge.nod=ct-1;
            adj[ct].push_back(edge);
        }
        prev_dist=*it;
    }
    first_real=ct+1;
    for(auto w:vec)
    {
        ct++;
        //ct<->d_to_ind[w.dist]
        edge.nod=d_to_ind[w.dist];
        edge.length=w.length;
        adj[ct].push_back(edge);
        edge.nod=ct;
        adj[d_to_ind[w.dist]].push_back(edge);
    }
    last_real=ct;
    int departe=farnode(first_real);
    int ras=farnode(departe);
    out<<dij[ras];

}