Farmer John quiere montar una foto panorámica de sus $N$ vacas en fila ($(1 \le N \le 200,000)$), numeradas como siempre de $1..N$. Toma $M$ fotos ($(1 \le M \le 100,000)$), cada una cubre un intervalo contiguo: la foto $i$ contiene las vacas de $a_i$ a $b_i$ inclusive. Las fotos juntas no necesariamente cubren todas las vacas.

FJ observa que cada foto contiene exactamente una vaca con manchas. Sabía que había algunas en el rebaño, pero nunca las contó. Determina el máximo número posible de vacas con manchas según las fotos. Si no existe una asignación de manchas compatible con las fotos, imprime $-1$.

Entrada

• Línea $1$: enteros $N$ y $M$.

• Líneas $2..M+1$: la línea $i+1$ contiene $a_i$ y $b_i$.

Salida

• Línea $1$: máximo número posible de vacas con manchas, o $-1$ si no hay solución.

Ejemplos

Entrada 1

5 3
1 4
2 5
3 4

Salida 1

1

Nota

Hay $5$ vacas y $3$ fotos. La primera contiene las vacas $1$ a $4$, etc.

La última indica que la vaca $3$ o la $4$ debe tener manchas. Cualquiera de las dos satisface también las dos primeras fotos.

Autor del problema: Brian Dean, 2013