Bessie fährt Bob und hofft auf Gewichtsvorteile auf $L$ Metern ($2 \le L \le 1,000,000,000$).

Starttempo ist $1$ m/s; unterwegs kann sie es ändern. Nahe der Mitte jedes Meters kann Schwerkraft um $1$ m/s beschleunigen oder Bremsen das Tempo halten oder um $1$ m/s reduzieren.

Bergab gibt es $N$ ($1 \le N \le 100,000$) Kurven. Kurve $i$ liegt $T_{i}$ Meter vom Start ($1 \le T_{i} \le L-1$); in diesen Meter muss sie mit höchstens $S_{i}$ m/s eintreten ($1 \le S_{i} \le 1,000,000,000$). Im Ziel ist jedes Tempo erlaubt.

Finde das höchste erreichbare Tempo ohne Verletzung der Kurvenlimits.

Ganze Zahlen sind Metermarken, Klammern Limits, etwa $[3]$:

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

Die Tabelle zeigt Tempo am Anfang jedes Meters:

Maximal $5$ nahe dem Anfang von Meter $4$.

Eingabe

• Zeile $1$: ganze Zahlen $L$, $N$ mit Leerzeichen.

• Zeilen $2..N+1$: Zeile $i+1$ beschreibt Kurve $i$ durch ganze Zahlen $T_{i}$, $S_{i}$ mit Leerzeichen.

Ausgabe

• Zeile $1$: ganze Zahl, höchstes Tempo von Start bis Ziel einschließlich beider.

Beispiele

Eingabe 1

14 3
7 3
11 1
13 8

Ausgabe 1

5

Aufgabenautor: Brian Jacokes, 2009