一年一度的gxoi杯跳远比赛又开始了，每个选手的跳远能力都非常强，单独比跳远距离难以分出胜负，所以比赛裁判长壮壮制定了一个独特的比赛规则: 跳远场地可以认为是一条数轴，在数轴上有M个互不相交的可起跳区间( 1≤M≤105)，区间左右端点均为整数（区间包括左右端点)，选手可以在这些可起跳区间内选择N( 2≤N≤105 )个整点（坐标为整数），选手的成绩就是被选中的点中任意两点之间距离最小值的最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
struct qtqj
{
	long long a,b;
}t[100005];
int maxv(long long a,long long b)
{
	if(a>b)return a;
	else return b;
}
bool cmp(qtqj a,qtqj b)
{
	return a.a<b.a;
}
int n,m;
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	long long l=0,r=0,mid;
	for(int i=1;i<=m;++i)
	{
		cin>>t[i].a>>t[i].b;
		r=maxv(t[i].a-t[i].b,r);
	}
	sort(t+1,t+m+1,cmp);
	while(l<r)
	{
		int cnt=-1;
		mid=(l+r)/2;
		for(int i=1;i<=m;++i)
		{
			int s=t[i].a;
			while(s<=t[i].b)
			{
				s+=mid;
				cnt++;
			}
		}
		if(cnt>m)r=mid-1;
		else if(cnt<m)l=mid+1;
		else
		{
			cout<<mid;
			break;
		}
	}
	return 0;
}