Farmer John gère sa ferme avec fiabilité, sauf pour tondre à temps. Il ne déplace sa tondeuse qu'une fois par jour. Le jour1 il commence en $(x_1, y_1)$, et le jour $d$ tond en ligne droite jusqu'à $(x_d, y_d)$, horizontalement ou verticalement sur la carte2D : $x_d = x_{d-1}$ ou $y_d = y_{d-1}$. Les mouvements horizontaux et verticaux alternent d'un jour au suivant.

Il progresse si lentement que l'herbe peut repousser avant la fin. Celle coupée le jour $d$ réapparaît le jour $d + T$. Si son trajet croise un trajet tondu au moins $T$ jours auparavant, il recoupe le même point. Pour améliorer sa mauvaise stratégie, FJ veut compter ces cas.

Comptez les croisements avec un ancien segment où l'herbe a repoussé. Ne comptez que les croisements « perpendiculaires » : point commun d'un segment horizontal et d'un vertical, qui n'est l'extrémité d'aucun.

Entrée

La première ligne contient $N$ ($2 \leq N \leq 100,000$) et $T$ ($1 \leq T \leq N$, $T$ pair).

Les $N$ lignes suivantes décrivent les positions de la tondeuse les jours $1 \ldots N$. La ligne $i$ contient les entiers $x_i$ et $y_i$, non négatifs et au plus $1,000,000,000$.

Sortie

Affichez le nombre de croisements décrits, où FJ recoupe de l'herbe déjà coupée puis repoussée.

Exemples

Entrée 1

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

Sortie 1

1

Remarque

Le jour7, FJ croise un segment tondu le jour2 : il compte. Les autres croisements ne comptent pas.

Remarque : limites étendues à5 secondes par cas (10 pour Python et Java) et512 MB de mémoire.

Auteurs du problème : Chad Waters et Brian Dean