Farmer John quer montar uma foto panorâmica das $N$ vacas alinhadas ($(1 \le N \le 200,000)$), numeradas como sempre de $1..N$. Tira $M$ fotos ($(1 \le M \le 100,000)$), cada uma cobre um intervalo contíguo: a foto $i$ contém as vacas $a_i$ até $b_i$ inclusive. Em conjunto, as fotos não necessariamente cobrem todas as vacas.

FJ percebe que cada foto contém exatamente uma vaca malhada! Sabia que havia algumas no rebanho, mas nunca as contou. Determine o máximo número possível de vacas malhadas segundo as fotos. Se não existir uma atribuição de manchas compatível com elas, imprima $-1$.

Entrada

• Linha $1$: inteiros $N$ e $M$.

• Linhas $2..M+1$: a linha $i+1$ contém $a_i$ e $b_i$.

Saída

• Linha $1$: máximo número possível de vacas malhadas, ou $-1$ se não houver solução.

Exemplos

Entrada 1

5 3
1 4
2 5
3 4

Saída 1

1

Note

Há $5$ vacas e $3$ fotos. A primeira contém as vacas $1$ a $4$, etc.

A última mostra que a vaca $3$ ou a $4$ deve ser malhada. Qualquer uma das duas satisfaz também as primeiras duas fotos.

Autor do problema: Brian Dean, 2013