题目描述

由于高传染性的牛传染病 $COWVID-19$ 的爆发，$PiPi$ 非常担忧他的奶牛们的健康。

为了限制疾病的传播，$PiPi$ 的 $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$。

数据范围

• 测试点 $2-3$ 满足 $b \leq 10^5$。
• 测试点 $4-10$ 没有额外限制。

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载