#include <bits/stdc++.h>
usingnamespacestd;typedeflonglongll;#define f first
#define s second
intN;llM;boolcheck(vector<pair<ll,ll>>v,lltarget){// target = max distancingllpos=v[0].f;lli=0;llamt=0;while(amt<N){if(v[i].f>=pos){pos=v[i].f;}if(v[i].f<=(pos)&&v[i].s>=(pos)){amt++;pos+=target;}else{i++;}if(i>=v.size()){returnfalse;}}returntrue;}llbinary_search(vector<pair<ll,ll>>x){llmax=x[x.size()-1].s-x[0].f;llp=0;for(lla=max;a>=1;a/=2){while((p+a)>=0&&check(x,p+a))p+=a;}returnp;}intmain(){ifstreamcin("socdist.in");ofstreamcout("socdist.out");cin>>N>>M;vector<pair<ll,ll>>nums(M);for(inti=0;i<M;i++){cin>>nums[i].f>>nums[i].s;}sort(nums.begin(),nums.end());cout<<binary_search(nums);}