Bessie partecipa al bob sperando che il peso elevato sia un vantaggio sui $L$ metri ($2 \le L \le 1,000,000,000$).

Parte a $1$ m/s ma può cambiare velocità. Vicino alla metà di ogni metro può accelerare per gravità di $1$ m/s o frenare per mantenere o ridurre di $1$ m/s.

Ci sono $N$ ($1 \le N \le 100,000$) curve in discesa. Curva $i$ è a $T_{i}$ metri dalla partenza ($1 \le T_{i} \le L-1$); deve entrare nel suo metro al massimo a $S_{i}$ m/s ($1 \le S_{i} \le 1,000,000,000$). All’arrivo ogni velocità è permessa.

Trova la velocità massima raggiungibile rispettando i limiti delle curve.

Gli interi sono metri e le parentesi limiti, ad esempio $[3]$:

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

La tabella dà le velocità all’inizio di ogni metro:

Il massimo era $5$ vicino all’inizio del metro $4$.

Input

• Riga $1$: interi $L$, $N$ separati da spazio.

• Righe $2..N+1$: riga $i+1$ descrive curva $i$ con interi $T_{i}$, $S_{i}$ separati da spazio.

Output

• Riga $1$: intero, massima velocità tra partenza e arrivo, inclusi.

Esempi

Input 1

14 3
7 3
11 1
13 8

Output 1

5

Autore del problema: Brian Jacokes, 2009