Description

Due to the outbreak of the highly contagious cow disease COWVID-19, Farmer John is very worried about the health of his cows.

To limit the spread of the disease, Farmer John’s $N$ cows ($2\le N\le 10^5$) decide to practice “social distancing” and spread out across the farm. The farm can be seen as a one-dimensional number line with $M$ disjoint intervals ($1\le M\le 10^5$) that contain grass available for grazing. The cows want to stand at different integer positions, where each chosen position has grass, and maximize the value of $D$, where $D$ is the distance between the closest two cows. Please help the cows find the maximum possible value of $D$.

Input Format

The first line contains $N$ and $M$. The following $M$ lines each contain two integers $a$ and $b$ describing an interval, where $0\le a\le b\le 10^{18}$. No two intervals overlap or touch at endpoints. A cow standing on an endpoint of an interval is considered to be standing on grass.

Output Format

Output the maximum possible value of $D$ such that the distance between every pair of cows is at least $D$. It is guaranteed that a solution with $D>0$ exists.

5 3
0 2
4 7
9 9

2

Hint

Sample Explanation

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

Subtasks

• Test cases $2$-$3$ satisfy $b\le 10^5$.
• Test cases $4$-$10$ have no additional constraints.

Translated by ChatGPT 5