Social Distancing#10307
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 cows have decided to practice "social distancing" and spread themselves out across the farm. The farm is shaped like a 1D number line, with 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 , where represents the distance between the closest pair of cows. Please help the cows determine the largest possible value of .
The first line contains (2 \le n \le 10^5) and (1 \le m \le 10^5). The next lines each describe an interval in terms of two integers and , where 0 \le a \le b \le 10^{18}. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of an interval counts as standing on grass.
Print the largest possible value of such that all pairs of cows are at least units apart. A solution with d > 0 is guaranteed to exist.
One way to achieve = is to have cows at positions , , , and .
Example 1