8023: Social Distancing

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

为了限制疾病的传播，Farmer John 的 N 头奶牛决定践行“社交距离”，分散到农场的各处。

农场的形状如一维数轴，上有 M 个互不相交的区间，其中有可用来放牧的青草。

奶牛们想要使她们位于不同的整数位置，每个位置上均有草，并且最大化 D 的值，其中 D 为最近的两头奶牛之间的距离。

请帮助奶牛们求出 D 的最大可能值。

输入格式

输入的第一行包含 N 和 M。

以下 M 行每行用两个整数 a 和 b 描述一个区间。

没有两个区间有重合部分或在端点处相交。

位于一个区间的端点上的奶牛视为在草上。

输出格式

输出 D 的最大可能值，使得所有奶牛之间的距离均不小于 D 单位。

保证存在 D>0 的解。

数据范围

2≤N≤105,

1≤M≤105,

0≤a≤b≤1018

输入样例：

5 3

0 2

4 7

9 9

输出样例：

2

样例解释

取到 D=2 的一种方式是令奶牛们处在位置 0、2、4、6 和 9。


Farmer John is worried for the health of his cows after an outbreak of the highly contagious bovine disease COWVID-19.

In order to limit transmission of the disease, Farmer John's N cows (2≤N≤105) have decided to practice "social distancing" and spread themselves out across the farm. The farm is shaped like a 1D number line, with M mutually-disjoint intervals (1≤M≤105) in which there is grass for grazing. The cows want to locate themselves at distinct integer points, each covered in grass, so as to maximize the value of D, where D represents the distance between the closest pair of cows. Please help the cows determine the largest possible value of D.

SAMPLE INPUT:

5 3
0 2
4 7
9 9

SAMPLE OUTPUT:

2

One way to achieve D=2 is to have cows at positions 0, 2, 4, 6 and 9.

Problem credits: Brian Dean