Bessie startuje w bobslejach, licząc na przewagę dużej masy na $L$ metrach ($2 \le L \le 1,000,000,000$).

Zaczyna z $1$ m/s, ale może zmieniać prędkość. Blisko środka każdego metra przyspiesza grawitacją o $1$ m/s lub hamuje, zachowując ją albo zmniejszając o $1$ m/s.

Podczas zjazdu jest $N$ ($1 \le N \le 100,000$) zakrętów. Zakręt $i$ jest $T_{i}$ metrów od startu ($1 \le T_{i} \le L-1$); trzeba wjechać w jego metr z najwyżej $S_{i}$ m/s ($1 \le S_{i} \le 1,000,000,000$). Meta dopuszcza dowolną prędkość.

Znajdź największą osiągalną prędkość bez łamania limitów zakrętów.

Całkowite oznaczają metry, nawiasy limity, np. $[3]$:

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

Tabela podaje prędkości na początku każdego metra:

Maksimum $5$ blisko początku metra $4$.

Wejście

• Wiersz $1$: całkowite $L$, $N$ ze spacją.

• Wiersze $2..N+1$: wiersz $i+1$ opisuje zakręt $i$ całkowitymi $T_{i}$, $S_{i}$ ze spacją.

Wyjście

• Wiersz $1$: całkowite, maksymalna prędkość od startu do mety włącznie.

Przykład

Wejście 1

14 3
7 3
11 1
13 8

Wyjście 1

5

Autor zadania: Brian Jacokes, 2009