题目描述

一年一度的 $gxoi$ 杯跳远比赛又开始了，每个选手的跳远能力都非常强，单独比跳远距离难以分出胜负，所以比赛裁判长壮壮制定了一个独特的比赛规则：

跳远场地可以认为是一条数轴，在数轴上有 $M$ 个互不相交的可起跳区间 $(1≤M≤10^5)$，区间左右端点均为整数 (区间包括左右端点)，选手可以在这些可起跳区间内选择 $N(2 \le N \le 10^5)$ 个整点 (坐标为整数)，选手的成绩就是被选中的点中任意两点之间距离最小值的最大值。

输入格式

第一行：两个数 $N$ 和 $M$，分别代表点的数量和区间的数量。

以下 $M$ 行：每行两个整数 $a$ 和 $b$，对应区间的左右端点。

数据保证任意两个区间都不重合。

输出格式

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

5 3
0 2
4 7
9 9

2

数据范围

对于 $10\%$ 的数据，$1 \le M \le 5,2 \le N \le 5$；

对于 $20\%$ 的数据，$1 \le M \le 1000,2 \le N \le 1000$；

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