题目描述

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

输入格式

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

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

对于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 \le b \le 10^{18}$。