测试数据来自 system/2193

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　由于新型肺炎传染病的爆发，小H 非常担忧他的精灵们的健康。

　　为了限制疾病的传播，精灵们的活动要保持适当的“社交距离”。精灵的活动场地形状如一维数轴，上面有 M 个互不相交的区间，这些区间中有精灵们赖以维持生命的食物。小H想要使精灵们位于数轴上不同的整数位置，且这些位置上必须有食物。

　　现在的问题是，在安排这些精灵后，需要最大化它们间的距离，也就是说，让最近的两个精灵之间的距离尽量大。请帮助精灵们求出这样的距离。

【输入格式】

　　输入的第一行包含 N 和 M。
以下 M 行每行用两个整数 a 和 b 描述一个区间。没有两个区间有重合部分或在端点处相交。注意区间的端点处也有食物，即区间是闭区间。

【输出格式】

　　输出一个距离值D，使得所有精灵之间的距离均不小于 D 单位。保证存在 D>0 的解。

【输入输出样例】

　Input

5 3
0 2
4 7
9 9

　Output

2

【输出格式解释】

　　取到 D=2 的一种方式是令精灵们处在位置 0、2、4、6 和 9。

【数据限制】

　　对于所有测试点满足，\(1≤M≤10^5\)、\(2≤N≤10^5\)，\(0≤a≤b≤10^18\)。
　　测试点 1-3 满足 \(b≤10^5、b≤10^5\)。
　　测试点 4-10 没有额外限制。

【来源】

　　Mr.he