#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n,M;
long long l=0,r=-(1<<30),a[MAXN],b[MAXN],d;
bool solve(long long m){
	long long cut=0,k=1;
	for(int i=1;i<=M;i++){
		if(b[i-1]<cut+m&&cut+m<a[i]){cut=a[i];k++;}
		while(a[i]<=cut+m&&cut+m<=b[i]){cut+=m;k++;}
		if(b[i]<cut+m&&cut+m<a[i+1]){cut=a[i+1];k++;}
	}
	if(k==n)return 1;
	else return 0;
}
int main(){
	cin>>n>>M;
	for(int i=1;i<=M;i++){
		cin>>a[i]>>b[i];
		r=max(r,b[i]);
	}
	while(l<r){
		long long mid=(l+r)/2;
		if(solve(mid)){
			d=mid;
			l=mid+1;
		}
		else r=mid;
	}
	cout<<d;
	return 0;
}