Bobsled Speed Limits

Bessie has entered a bobsled competition on a course of length \(L\) meters (\(2 \le L \le 10^9\)). She starts at a speed of 1 meter per second at the beginning of the course (position 0). For each meter she travels, in the middle of that meter she is allowed to change her speed: she may accelerate by 1 m/s (using gravity), maintain her current speed, or decelerate by 1 m/s.

Along the course, Bessie must navigate \(N\) turns (\(1 \le N \le 10^5\)). The \(i\)th turn is located at \(T_i\) meters from the start (\(1 \le T_i \le L-1\)) and she must enter that meter at a speed no more than \(S_i\) m/s (\(1 \le S_i \le 10^9\)). There is no speed limit at the finish line (position \(L\)).

Your task is to compute the maximum speed Bessie can achieve at any point along the course without violating any turn speed limits.

Hint

You may consider the course as a sequence of key positions: the start (position 0 with speed fixed at 1 m/s), the turn positions (each with its speed limit), and the finish (position \(L\) with no effective limit). One effective approach is to perform a forward pass to propagate the acceleration constraints and a backward pass to ensure deceleration is feasible at turn positions. Moreover, within intervals between two key positions with speeds \(a\) and \(b\) separated by distance \(d\), the maximum speed attainable obeys the relation \[ (m - a) + (m - b) \le d \quad\Longrightarrow\quad m \le \frac{d + a + b}{2}. \] Using this, you can determine the overall maximum speed possible on the course.

inputFormat

The first line contains two space-separated integers \(L\) and \(N\): the length of the course and the number of turns.

Each of the next \(N\) lines contains two space-separated integers \(T_i\) and \(S_i\) representing the position of a turn and its speed limit. The turns may be given in arbitrary order.

outputFormat

Output a single integer: the maximum speed (in m/s) Bessie can achieve during her run without exceeding any turn speed limits.

sample

14 3
7 3
11 1
13 8

5