Bessie compite en bobsleigh esperando ventaja por su gran peso en la pista de $L$ metros ($2 \le L \le 1,000,000,000$).

Sale a $1$ m/s y puede variar la velocidad. Cerca del medio de cada metro puede acelerar por gravedad $1$ m/s o frenar para mantenerla o reducir $1$ m/s.

Hay $N$ ($1 \le N \le 100,000$) curvas cuesta abajo. Curva $i$ está a $T_{i}$ metros de salida ($1 \le T_{i} \le L-1$); debe entrar en su metro a como máximo $S_{i}$ m/s ($1 \le S_{i} \le 1,000,000,000$). Puede cruzar la meta a cualquier velocidad.

Halla la velocidad máxima alcanzable respetando las curvas.

Los enteros son marcas de metros y corchetes límites, por ejemplo $[3]$:

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

Estas son velocidades al inicio de cada metro:

El máximo fue $5$ cerca del inicio del metro $4$.

Entrada

• Línea $1$: enteros $L$, $N$ separados por espacio.

• Líneas $2..N+1$: línea $i+1$ describe curva $i$ con enteros $T_{i}$, $S_{i}$ separados por espacio.

Salida

• Línea $1$: entero, velocidad máxima entre salida y meta, inclusive.

Ejemplos

Entrada 1

14 3
7 3
11 1
13 8

Salida 1

5

Autor del problema: Brian Jacokes, 2009