The sick cows decided to help Farmer John.
In order to limit disease transmission, N (2 ≤ N ≤ 10
5) FD cows decided to practice "social distancing" and "distributed" on the farm. The farm is represented as a straight line, with M intervals (1 ≤ M ≤ 10
5) that do not have common points, on which grass grows. The cows want to spread out at points with different coordinates, each point covered with grass, so as to maximize the value of D. Where D represents the distance between the nearest pair of cows. Help the cows determine the highest D value.
Input
The first line of input contains N and M. Each of the next M lines describes an interval with two integers a and b, where 0 ≤ a≤ b ≤10
18. No two intervals overlap or touch at their endpoints. A cow standing at the end point of the interval is considered to be standing on grass.
Imprint
Print the largest possible value of D such that all pairs of cows are at least D units apart. It is guaranteed that there is a solution with D>0.
Examples
| # |
Input |
Output |
| 1 |
5 3
0 2
47
9 9
| 2 |