Bessie se ha inscrito en una competencia de trineo porque ella espera que su asombroso peso le dé a ella una ventaja a través del trayecto de ~L~ metros.

Bessie saldrá de la línea de partida con una velocidad de 1 metro por segundo, pero su velocidad puede cambiar conforme ella se desplaza a través del trayecto. Cerca de la mitad de cada metro que Bessie atraviesa, ella puede cambiar su velocidad o usando la gravedad para acelerar un metro por segundo o frenando para permanecer con la misma velocidad o disminuyendo su velocidad un metro por segundo.

Naturalmente, Bessie debe maniobrar ~N~ curvas en el camino hacia abajo. La curva ~i~ está ubicada ~T_i~ metros a partir del inicio de la trayectoria, y ella debe entrar en el metro de la curva con una velocidad de a lo más ~S_i~ metros por segundo. Bessie puede cruzar la línea de llegada con la velocidad que ella quiera.

Ayude a Bessie a conocer la velocidad más alta a la que puede llegar sin excederse de los límites de velocidad en las curvas.

Considere esta trayectoria con los metros marcados como enteros y los límites de velocidad en corchetes (por ejemplo ~[3]~):

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

A continuación hay un cuadro con las velocidades de Bessie al inicio y al final de cada metro de longitud de la trayectoria:

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

Su máxima velocidad fue 5 cerca al inicio del metro 4.

Entrada

• Línea 1: Dos enteros separados por espacio: ~L~ y ~N~.
• Líneas 2..N+1: La línea i+1 describe la curva ~i~ con dos enteros separados por espacio: ~T_i~ y ~S_i~.

Salida

Un solo entero, representando la velocidad máxima que puede ser obtenida por Bessie entre el inicio y la línea de fin, inclusive.

Restricciones

• ~2 \leq L \leq 1,000,000,000~
• ~1 \leq N \leq 100,000~
• ~1 \leq T_i \leq L-1~
• ~1 \leq S_i \leq 1,000,000~

Ejemplo de Entrada

14 3
7 3
11 1
13 8

Ejemplo de Salida

5

USACO DEC09 Problem bobsled