O “chão virou lava” é uma brincadeira infantil muito popular. No contexto desse problema, para jogar basta imaginar que o chão do ambiente é um rio de lava é portando não pode ser pisado diretamente, ou seja, só é permitido que o jogador pise em lugares ditos seguros como almofadas mágicas.

Dois irmãos Gabriel e Eduardo estão vendo um filme muito popular, chamado “Efeito Devastador Assustador 2”, também conhecido como EDA2. Gabriel aproveitou um dos intervalos do filme para pegar mais pipoca. Quando Gabriel estava voltando para o sofá, com o balde de pipoca na mão, no momento em que Gabriel estava na posição $O$ do plano cartesiano de coordenadas inteiras foi surpreendido pelo grito seu irmão.

“o chão virou lava”

A partir daquele momento Gabriel só poderia voltar para o sofá no ponto $S$ pisando no ponto inicial $O$ ou em $N$ almofadas mágicas distribuídas em pontos distinto e inteiros do plano cartesiano. Como Gabriel está com um balde de pipoca na mão ele só pode dar passo suaves entre as almofadas, ou seja, dada duas almofadas mágicas quaisquer localizadas nos pontos $A$ e $B$ do plano cartesiano, Gabriel só pode se mover de $A$ para $B$ se a distância euclidiana entre os pontos $A$ e $B$ for menor ou igual a distância $d$ do seu passo.

Entrada

A entrada é composta por um único caso de teste. A primeira linha, do caso de teste, contém um número inteiro $d$, onde $1 \leq d \leq 10^{3}$, representando o tamanho do passo do Gabriel. A segunda linha contém um número inteiro $n$, onde $2 \leq n \leq 3*10^{3}$. A terceira linha do caso de teste contém dois números inteiros $o_{x}$ e $o_{y}$, onde $-10^{5} \leq o_{x}, o_{y} \leq 10^{5}$ que correspondem às coordenadas do ponto $O$, a localização inicial do Gabriel. A quarta linha, do caso de teste, contém dois números inteiros $s_{x}$ e $s_{y}$, onde $-10^{5} \leq s_{x}, s_{y} \leq 10^{5}$, correspondendo às coordenadas do ponto $S$, a localização do sofá. As próximas $n-2$ linhas possuem dois inteiros $x_{i}$ e $y_{i}$, onde $-10^{5} \leq x_{i}, y_{i} \leq 10^{5}$ indicando a coordenada da $i$-ésima almofada.

Saída

Imprima na saída padrão o menor número de passo que Gabriel precisa fazer para chegar no sofá localizado no ponto $S$ partindo do ponto $O$. Caso seja impossível imprima –1.

Exemplos

Exemplo de entrada

3
8
4 2
7 4
5 2
3 4
7 3
6 4
7 2
4 3

Saída para o exemplo acima

2

Gabriel pode pisar somente nas almofadas mágicas. Na figura abaixo, os pontos cartesianos $A,B,C,D,E,F$ representam as almofadas. O pontos $O$ e $S$ representam, respectivamente, o ponto de origem e o sofá, o destino de nosso herói.

Para caminhar, Gabriel poderá pisar somente nas almofadas a seu alcance (na figura abaixo, representada pelo círculo).

A partir do ponto $O$, Gabriel, pode pisar somente nas almofadas $A,B,E,D,F$. Para alcançar o sofá, $S$, deverá pisar em alguma almofada intermediária para, então, poder chegar no sofá.

Exemplo de entrada

5
7
0 0
11 4
2 2
2 4
8 0
6 2
4 7

Saída para o exemplo acima

4

Exemplo de entrada

7
11
0 0
22 16
18 12
12 0
22 8
12 4
18 4
6 12
6 2
10 20
18 24

Saída para o exemplo acima

6

Exemplo de entrada

4
11
0 0
22 16
18 12
12 0
22 8
12 4
18 4
6 12
6 2
10 20
18 24

Saída para o exemplo acima

-1