Description

Bessie has entered a bobsled competition because she hopes her hefty weight will give her an advantage over the $L$ meter course ($2 \le L \le 10^9$).

Bessie pushes off the starting line at $1$ meter per second, and her speed can change while she travels along the course. Near the middle of every meter Bessie covers, she can change her speed by using gravity to accelerate by $1$ meter per second, or by braking to keep the same speed or decrease her speed by $1$ meter per second.

On the way down the hill, Bessie must negotiate $N$ turns ($1 \le N \le 10^5$). Turn $i$ is located $T_i$ meters from the start ($1 \le T_i < L$), and she must enter the meter that contains turn $i$ at a speed of at most $S_i$ meters per second ($1 \le S_i \le 10^9$). Bessie may cross the finish line at any speed.

Help Bessie determine the maximum speed she can attain anywhere on the course without exceeding the speed limits at the turns.

Consider this course with the meter markers as integers and the turn speed limits in brackets (for example, "[3]"):

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

Below is a chart of Bessie's speeds at the beginning of each meter along the course:

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 

Her maximum speed was $5$ near the beginning of meter $4$.

Input Format

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

Output Format

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

14 3 
7 3 
11 1 
13 8 

5