Farmer John vuole comporre una foto panoramica delle sue $N$ mucche in fila ($(1 \le N \le 200,000)$), numerate come sempre da $1..N$. Scatta $M$ foto ($(1 \le M \le 100,000)$), ciascuna copre un intervallo contiguo: la foto $i$ contiene le mucche da $a_i$ a $b_i$ comprese. Le foto insieme non coprono necessariamente tutte le mucche.

FJ nota che ogni foto contiene esattamente una mucca maculata! Sapeva di averne alcune, ma non le aveva mai contate. Determina il massimo numero possibile di mucche maculate in base alle foto. Se nessuna assegnazione di macchie è compatibile con esse, stampa $-1$.

Input

• Riga $1$: interi $N$ e $M$.

• Righe $2..M+1$: la riga $i+1$ contiene $a_i$ e $b_i$.

Output

• Riga $1$: massimo numero possibile di mucche maculate, oppure $-1$ se non esiste soluzione.

Esempi

Input 1

5 3
1 4
2 5
3 4

Output 1

1

Note

Ci sono $5$ mucche e $3$ foto. La prima contiene le mucche $1$ a $4$, ecc.

L'ultima mostra che la mucca $3$ o la $4$ deve essere maculata. Scegliere una qualsiasi delle due soddisfa anche le prime due foto.

Autore del problema: Brian Dean, 2013