#p3353. [USACO20OPEN S Social Distancing]社交距离

[USACO20OPEN S Social Distancing]社交距离

原题来自:USACO20OPEN S Social Distancing

题目描述

由于高传染性的牛传染病 COWVID-19 的爆发,Farmer John 非常担忧他的奶牛们的健康。

为了限制疾病的传播,Farmer John 的 NN 头奶牛(2≤N≤1052\le N\le 10^5)决定践行“社交距离”,分散到农场的各处。

农场的形状如一维数轴,上有 MM 个互不相交的区间(1≤M≤1051\le M\le 10^5),其中有可用来放牧的青草。奶牛们想要使她们位于不同的整数位置,每个位置上均有草,并且最大化 DD 的值,其中 DD 为最近的两头奶牛之间的距离。请帮助奶牛们求出 DD 的最大可能值。

输入格式

输入的第一行包含 NN 和 MM。以下 MM 行每行用两个整数 aa 和 bb 描述一个区间,其中 0≤a≤b≤10180\le a\le b\le 10^{18}。没有两个区间有重合部分或在端点处相交。位于一个区间的端点上的奶牛视为在草上。

输出格式

输出 DD 的最大可能值,使得所有奶牛之间的距离均不小于 DD 单位。保证存在 D>0D>0 的解。

样例

输入样例1

5 3

0 2

4 7

9 9

输出样例1

2

样例解释1

取到 D=2D=2 的一种方式是令奶牛们处在位置 00、22、44、66 和 99。

数据范围与提示

  • 测试点 22-33 满足 b≤105b\le 10^5。

  • 测试点 44-1010 没有额外限制。