本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

在高度传染的牛类疾病 COWVID-19 爆发后，Farmer John 担心他的奶牛健康状况。 为了限制疾病传播，Farmer John 的 $N$ 头奶牛（$2 \leq N \leq 10^5$）决定进行“社交距离”，在农场里分散开来。农场可以看作一条一维数轴，其中有 $M$ 个两两互不相交的区间（$1 \leq M \leq 10^5$），这些区间内有草可供放牧。奶牛希望站在互不相同的整数点上，且每个点都必须有草覆盖，以最大化 $D$ 的值，其中 $D$ 表示任意两头奶牛中最近的一对之间的距离。请帮助奶牛确定 $D$ 的最大可能值。

输入格式

第一行输入包含 $N$ 和 $M$。接下来的 $M$ 行每行用两个整数 $a$ 和 $b$ 描述一个区间，其中 $0 \leq a \leq b \leq 10^{18}$。任意两个区间不会重叠，也不会在端点处相接。一头奶牛站在区间端点上也算站在草地上。

输出格式

输出最大的可能值 $D$，使得任意两头奶牛之间都至少相距 $D$ 个单位。保证存在 $D>0$ 的解。

5 3
0 2
4 7
9 9

2

提示

一种实现 $D=2$ 的方式是让奶牛站在位置 $0$、$2$、$4$、$6$ 和 $9$。 SCORING: 测试点 2-3 满足 $b\le 10^5.$ 测试点 4-10 没有额外限制。 题目来源：Brian Dean

来源

USACO|2020|Silver