选点

来源：2024 年 51NOD 普及组模拟第 7 套，第 3 题；同模型原题 USACO 2020 US Open Silver Social Distancing（洛谷 P6281）。

题目限制

2000 ms，256 MiB；文件读写（本次比赛设置）。

题目描述

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

文件读写要求

本题必须从 faraway.in 读取输入，并将答案写入 faraway.out。文件名区分大小写。

C++ 程序可在 main 函数开始处使用：

freopen("faraway.in", "r", stdin);
freopen("faraway.out", "w", stdout);

输入格式

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

输出格式

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

数据范围

对于 $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}$ 。

输入样例 1

5 3
0 2
4 7
9 9

输出样例 1

2

本次模拟计分

共25个测试点，采用分组全过计分：第一组10分，满足 $N,M\le5$；第二组10分，满足 $N,M\le1000$；第三组80分，无额外限制。每组内所有测试点均通过，才能获得该组分数。