Farmer John é fiável a gerir a quinta, exceto a cortar a relva a tempo. Só move a máquina uma vez por dia. No dia1 começa em $(x_1, y_1)$ e no dia $d$ corta em linha reta até $(x_d, y_d)$, horizontal ou verticalmente no mapa2D: $x_d = x_{d-1}$ ou $y_d = y_{d-1}$. Alterna movimentos horizontais e verticais em dias sucessivos.

Avança tão devagar que a relva pode voltar a crescer antes de terminar. A cortada no dia $d$ reaparece no dia $d + T$. Ao cruzar um trajeto cortado pelo menos $T$ dias antes, corta o mesmo ponto de novo. Para melhorar a má estratégia, quer contar esses casos.

Conte cruzamentos com segmentos anteriores onde a relva já voltou a crescer. Só conte cruzamentos «perpendiculares»: ponto comum a um segmento horizontal e um vertical que não seja extremo de nenhum.

Entrada

A primeira linha contém $N$ ($2 \leq N \leq 100,000$) e $T$ ($1 \leq T \leq N$, $T$ par).

As $N$ linhas seguintes descrevem as posições da máquina nos dias $1 \ldots N$. A linha $i$ contém inteiros $x_i$ e $y_i$, não negativos e no máximo $1,000,000,000$.

Saída

Imprima o número de cruzamentos descritos, onde FJ volta a cortar relva anteriormente cortada e crescida.

Exemplos

Entrada 1

7 4
0 10
10 10
10 5
3 5
3 12
6 12
6 3

Saída 1

1

Nota

No dia7 cruza um segmento cortado no dia2, que conta. Os restantes cruzamentos não contam.

Nota: limites alargados a5 segundos por caso (10 para Python e Java) e512 MB de memória.

Autores do problema: Chad Waters e Brian Dean