Farmer John gestiona su granja fiablemente salvo al segar a tiempo. Solo mueve la segadora una vez al día. El día1 empieza en $(x_1, y_1)$ y el día $d$ siega en línea recta hasta $(x_d, y_d)$, horizontal o verticalmente en el mapa2D: $x_d = x_{d-1}$ o $y_d = y_{d-1}$. Alterna movimientos horizontales y verticales en días consecutivos.

Avanza tan despacio que la hierba puede volver a crecer antes de terminar. La cortada el día $d$ reaparece el día $d + T$. Si cruza un camino segado al menos $T$ días antes, corta de nuevo el mismo punto. Para mejorar su mala estrategia quiere contar estos casos.

Cuenta los cruces con segmentos anteriores donde la hierba ya creció de nuevo. Solo cuentan cruces «perpendiculares»: punto común de un segmento horizontal y uno vertical que no es extremo de ninguno.

Entrada

La primera línea contiene $N$ ($2 \leq N \leq 100,000$) y $T$ ($1 \leq T \leq N$, $T$ par).

Las siguientes $N$ líneas describen las posiciones de la segadora los días $1 \ldots N$. La línea $i$ contiene enteros $x_i$ y $y_i$, no negativos y como máximo $1,000,000,000$.

Salida

Imprime la cantidad de cruces descritos, donde vuelve a cortar hierba ya cortada y regenerada.

Ejemplos

Entrada 1

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

Salida 1

1

Nota

El día7 cruza un segmento cortado el día2, que cuenta. Los otros cruces no cuentan.

Nota: límites ampliados a5 segundos por caso (10 para Python y Java) y512 MB de memoria.

Autores del problema: Chad Waters y Brian Dean