站外题求助 QWQ

相邻点距

题面

一个数轴上有M个不相交的区间[a,b]，现在要求你在这些区间中选N个点（每个点都必须落在一个整数位置），并且要求尽可能的让相邻的两个点位置离得远一点，那么离得最近的两个相邻点距离是多少？

输入 输入第1行两个整数N和M；

接下来输入M行，每行两个整数a，b，表示区间的左右端点。

输出 输出一个整数，表示两个最近的相邻点的距离。保证输出有解。

样例输入 1

5 3 0 2 4 7 9 9

样例输出 1

2

样例输入 2

4 3 6 40 1 4 50 100 样例输出 2

33 数据范围

2≤N≤10^5

1≤M≤10^5

0≤a≤b≤10^18

样例1解释：

5个点可以分别位置数轴的0,2,4,6,9这五个位置。