eolymp
bolt
Try our new interface for solving problems
Problems

Social Distancing

Social Distancing

Time limit 1 second
Memory limit 128 MiB

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 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 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.

Input data

The first line contains n (2n10^5) and m (1m10^5). The next m lines each describe an interval in terms of two integers a and b, where 0ab10^18. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of an interval counts as standing on grass.

Output data

Print the largest possible value of d such that all pairs of cows are d units apart. A solution with d > 0 is guaranteed to exist.

Example

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

prb10307.gif

Examples

Input example #1
5 3
0 2
4 7
9 9
Output example #1
2
Source 2020 USACO US Open, Silver