Bessie compete em bobsleigh, esperando vantagem do grande peso na pista de $L$ metros ($2 \le L \le 1,000,000,000$).

Parte a $1$ m/s e pode mudar velocidade. Perto do meio de cada metro pode acelerar pela gravidade $1$ m/s ou travar para manter ou reduzir $1$ m/s.

Há $N$ ($1 \le N \le 100,000$) curvas na descida. Curva $i$ fica a $T_{i}$ metros da partida ($1 \le T_{i} \le L-1$); entra nesse metro no máximo a $S_{i}$ m/s ($1 \le S_{i} \le 1,000,000,000$). Pode cruzar a chegada a qualquer velocidade.

Determine a maior velocidade alcançável respeitando os limites das curvas.

Os inteiros são marcas de metros e os colchetes limites, por exemplo $[3]$:

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

Eis velocidades no início de cada metro:

O máximo foi $5$ perto do início do metro $4$.

Entrada

• Linha $1$: inteiros $L$, $N$ separados por espaço.

• Linhas $2..N+1$: linha $i+1$ descreve curva $i$ por inteiros $T_{i}$, $S_{i}$ separados por espaço.

Saída

• Linha $1$: inteiro, velocidade máxima entre partida e chegada, inclusive.

Exemplos

Entrada 1

14 3
7 3
11 1
13 8

Saída 1

5

Autor do problema: Brian Jacokes, 2009