30分求调

#include <bits/stdc++.h>
using namespace std;
long long n,m,maxx;
struct node{
	long long a,b;
}q[100005];
bool cmp(node a,node b){
	return a.a < b.a;
}
long long check(long long mid){
	long long w = -1e18,i = 1,cnt = 1;
	for(i = 1;i <= n;i++){
		if(i == 1) w = q[cnt].a;
		else w = max(w+mid,q[cnt].a);
		if(w > maxx) {
			i--;
			break;
		}
		if(i >= n) return 1;
		if(w+mid > q[cnt].b) cnt++;
		if(cnt > m){
			i--;
			break;
		}
	}
	cout << endl;
	if(i >= n) return 1;
	return 0;
	
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(long long i = 1;i <= m;i++){
		cin >> q[i].a >> q[i].b;
	} 
	sort(q+1,q+m+1,cmp);
	long long l = 1,r = q[m].b-q[1].a;
	maxx = q[m].b;
	long long ans = 1;
	while(l <= r){
		long long mid = (l+r)/2;
		if(check(mid)){
			ans = max(ans,mid);
			l = mid+1;
		}
		else r = mid-1;
	}
	cout << ans << endl;
	return 0;
}