#include <bits/stdc++.h>
using namespace std;
int n,m,dn,d;
struct node{
    long long x,y;
}a[100001];
bool jzh(long long x){
	int u=a[1].x;
	int sum=1;
	int q=u+x;
	while(q<=d){
        for(int i=1;i<=m;i++) if(a[i].x<=q && a[i].y>=q){
            sum++;
            q+=u;
        }
    }
	return sum>=n;
}
int main(){
	cin>>n>>m;
	long long l=1,r=0,x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		a[i].x=x;
		a[i].y=y;
        r=max(r,y);
	}
    d=r;
	long long mid;
	while(l<=r){
		mid=(l+r)/2;
		if(jzh(mid)==true){
			dn=mid;
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	cout<<dn;
    return 0;
}