#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
long long N, M;
long long a[100005];
long long b[100005];
long long ans;
long long maxd;
char check(long long myd) //return '>' '=' and '<'
{
long long nowpos = a[0]; //不一定从0开始
long long cowleft = N - 1;
for (long long k = 0; k < M; k++) //mising k=0
{
while (nowpos <= b[k])
{
if (nowpos + myd < a[k])
{
nowpos = a[k];
}
else
{
if (nowpos + myd <= b[k])
nowpos += myd;
else //missing
// continue; break?
break;
}
if (nowpos >= a[k] and nowpos <= b[k])
cowleft--;
}
}
if (cowleft < 0)
{
return '<';
}
if (cowleft > 0)
return '>';
else
return '=';
}
int main(void)
{
freopen("7.in", "r", stdin);
// freopen("socdist.out", "w", stdout);
cin >> N >> M;
for (long long _ = 0; _ < M; _++)
{
cin >> a[_] >> b[_];
}
// --36266
sort(a, a + M);
sort(b, b + M); //less first
// cout<<"--"<<a[0]<<endl;
maxd = b[M - 1] / N;
long long l = 0;
long long r = maxd + 2;
long long mid = (r + l) / 2;
// cout << maxd; //get 1?
while (1)
{
mid = (r + l) / 2; //missing
cout << mid << endl;
char tmp_ans = check(mid);
cout << tmp_ans << endl;
if (tmp_ans == '=')
{
cout << mid << endl; //得到了2还是死循环,2还是小于
// exit(0);
}
// 不要?当小于?
if (tmp_ans == '<' or tmp_ans=='=') //反了
{
l = mid;
}
else
{
if (check(mid - 1) != '>')
{
// cout<<"aa";
cout << mid - 1 << endl;
exit(0);
}
r=mid;
}
}
// for (long long a = 1; a <= r; a++)
// {
// // cout<<a<<endl;
// // cout<<check(a)<<endl;
// if (check(a) == '>')
// {
// cout << a -1 << endl;
// break;
// }
// }
return 0;
}