Bobsledding

Bessie has entered a bobsled competition on a course that is $L$ meters long ($2 \le L \le 1{,}000{,}000{,}000$).

She pushes off the starting line at a speed of $1$ meter per second. Near the middle of every meter she travels she may adjust her speed in exactly one of three ways: use gravity to accelerate by $1,\text{m/s}$, keep the same speed, or brake to slow down by $1,\text{m/s}$. Consequently, her speed at the start of one meter and her speed at the start of the next meter differ by at most $1$.

The course has $N$ turns ($1 \le N \le 100{,}000$). Turn $i$ is located $T_i$ meters from the start ($1 \le T_i \le L-1$), and Bessie must enter that meter marker (marker $T_i$) at a speed of at most $S_i,\text{m/s}$ ($1 \le S_i \le 1{,}000{,}000{,}000$). She may cross the finish line at any speed.

Determine the fastest speed Bessie can attain at any point between the start and the finish, inclusive.

Here, "the speed at meter marker $k$" means her speed as she passes the $k$-meter point, i.e. the speed at which she begins running the $(k+1)$-th meter. Her speed at marker $0$ is always $1$.

The figure below shows the course. Integers are meter markers, and a number in brackets is that turn's speed limit (e.g. [3]).

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
Start                         + 8
                               \
                                + 9
                                 \
                                  + 10       +++ 14 (finish)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

The table below shows Bessie's speed as she passes each meter marker on the course above.

Max:                              3               1       8
Mtrs: 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
Spd:  1   2   3   4   5   5   4   3   4   3   2   1   2   3   4

In this case her top speed is $5$, reached near meter marker $4$.

• Line 1: Two space-separated integers, $L$ and $N$.
• Lines 2 to $N+1$: Line $i+1$ describes turn $i$ with two space-separated integers, $T_i$ and $S_i$.

• A single integer: the maximum speed Bessie can attain between the start and the finish line, inclusive.