#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+50;
pair<ll, ll> Przedzialy[N];

int CzyMoznaRozmiescic(int n, int m, ll d){
	ll ostatni = -2*d;
	ll wynik = 0;
	for(int i=1; i<=m; i++){
		while( max(ostatni+d, Przedzialy[i].first) <= Przedzialy[i].second ){
			wynik++;
			ostatni = max(ostatni+d, Przedzialy[i].first);
			if ( wynik >= (ll)n ) return 1;
		}
	}
	return 0;
}

ll LiczWynik(int n, int m){ 
	ll p, k, s;
	p = 0;
	k = (ll)1e18;
	while(p<k){
		s=(p+k+1)/2;
		if( CzyMoznaRozmiescic(n, m, s) ) p=s;
		else k=s-1;
	}
	return p;
}

int main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 freopen("socdist.in", "r", stdin);
 freopen("socdist.out", "w", stdout);
	int n, m;
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		cin>>Przedzialy[i].first>>Przedzialy[i].second;
	}
	sort(Przedzialy+1, Przedzialy+1+m);
	cout << LiczWynik(n, m) << "\n";
	return 0;
}