Bessie participe au bobsleigh, espérant que son poids élevé l’avantagera sur $L$ mètres ($2 \le L \le 1,000,000,000$).

Elle part à $1$ m/s et peut changer de vitesse. Vers le milieu de chaque mètre, la gravité peut ajouter $1$ m/s, ou le freinage maintenir la vitesse ou retrancher $1$ m/s.

Elle négocie $N$ ($1 \le N \le 100,000$) virages en descente. Le virage $i$ est à $T_{i}$ mètres du départ ($1 \le T_{i} \le L-1$) ; elle entre dans ce mètre à au plus $S_{i}$ m/s ($1 \le S_{i} \le 1,000,000,000$). L’arrivée se franchit à toute vitesse.

Trouvez la vitesse maximale atteignable sans dépasser les limites des virages.

Ci-dessous les entiers sont les mètres, les crochets les limites, par exemple $[3]$ :

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
Départ                         + 8    
                               \
                                + 9    
                                 \
                                  + 10       +++ 14 (arrivée)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

Voici les vitesses au début de chaque mètre :

Le maximum est $5$ près du début du mètre $4$.

Entrée

• Ligne $1$ : entiers $L$, $N$ séparés par un espace.

• Lignes $2..N+1$ : ligne $i+1$, virage $i$ par entiers $T_{i}$, $S_{i}$ séparés par un espace.

Sortie

• Ligne $1$ : entier, vitesse maximale du départ à l’arrivée, bornes incluses.

Exemples

Entrée 1

14 3
7 3
11 1
13 8

Sortie 1

5

Auteur du problème : Brian Jacokes, 2009