有 M 个互不相交的区间（ 1≤M≤10^5 ），左右端点均为整数（区间包括左右端点），在这些区间内选择 N （ 2≤N≤10^5 ）个整点（坐标为整数），使得任意相邻两点之间的最小距离尽可能远，问这个最远的距离是多少？

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

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

对于10%的数据，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。

输入样例

5 3

0 2

4 7

9 9

输出样例

2