Social Distancing on the Farm

Due to the outbreak of the highly contagious bovine disease COWVID-19, Farmer John is very worried about the health of his cows. To prevent the spread of the disease, his N cows (where \(2 \leq N \leq 10^5\)) have decided to practice social distancing by spreading out across the farm.

The farm is represented as a one-dimensional number line, and there are M non-overlapping intervals (with \(1 \leq M \leq 10^5\)) where grass is available. Each cow must occupy a distinct integer position within these intervals, and every such integer position contains grass. The cows wish to maximize \(D\), the minimum distance between any two cows. Help them determine the maximum possible value of \(D\).

inputFormat

The first line contains two integers (N) and (M). Each of the next (M) lines contains two integers (L) and (R), representing an interval [L, R] (inclusive) with available grass. All intervals are non-overlapping.

outputFormat

Output a single integer representing the maximum possible minimum distance (D) between any two cows.

sample

2 1
1 5

4