Cobertura Mínima

#177
Made by: Crazynds
100MB
0.1s

Você possui um segmento de reta de comprimento $L$, representando o intervalo $[0, L]$, e $N$ faixas de pintura, cada uma cobrindo o intervalo $[a_i, b_i]$.

Você quer pintar o segmento inteiro $[0, L]$ usando o menor número possível de faixas. Cada faixa pode ser usada no máximo uma vez. Determine quantas faixas são necessárias, ou diga que é impossível.

Input

A primeira linha contém dois inteiros $L$ e $N$ $(1 \le L \le 10^9,\ 1 \le N \le 10^5)$.

As próximas $N$ linhas contêm dois inteiros $a_i$ e $b_i$ $(0 \le a_i < b_i \le 10^9)$, representando os extremos de cada faixa.

Output

Imprima um único inteiro: o número mínimo de faixas para cobrir $[0, L]$, ou $-1$ se for impossível.

Input Example
Output Example 
10 5
0 4
2 7
5 9
6 10
3 6
3

Explanation 1:
Uma seleção ótima é: - $[0, 4]$ - $[2, 7]$ - $[6, 10]$ Essas três faixas cobrem completamente $[0, 10]$. 

4 4
0 1
1 2
2 3
3 4

4

4 16
3 5
0 5
4 7
1 7
2 8
0 6
1 4
4 6
0 5
2 7
2 5
0 9
4 7
0 7
0 5
0 8

1

60 12
48 55
0 34
12 34
36 63
50 59
24 39
22 55
34 60
6 40
21 29
18 39
31 52

2

86 18
4 32
25 76
62 72
81 85
61 63
72 89
13 22
71 74
14 21
17 81
73 91
17 36
18 51
5 24
44 88
25 52
8 12
80 85

-1