跳远比赛(jump)

【题目描述】

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

【输入格式】

第一行:两个数N和M，分别代表点的数量和区间的数量:以下 M行:每行两个整数a和b，对应区间的左右端点。数据保证任意两个区间都不重合。

【输出格式】

输出可能的最远的距离是多少。

【输入样例1】

5 3
0 2
4 7
9 9

配套文件参看 jump1.in

【输出样例1】

2

配套文件参看 jump1.ans

【输入样例 2】

配套文件参看 jump2.in

【输出样例 2】

配套文件参看 jump2.ans

【数据范围】

对于18%的数据，$1≤M≤5，2≤N≤5$

对于20%的数据，$1≤M≤1000，2≤N≤1000;$

对于100%的数据,$1≤M≤10^5,2≤N≤10^5, 0≤a≤b≤10^{18}。$