Farmer John führt seine Farm zuverlässig, außer beim rechtzeitigen Mähen. Er bewegt den Mäher nur einmal täglich. Am Tag1 startet er bei $(x_1, y_1)$ und mäht am Tag $d$ geradlinig bis $(x_d, y_d)$, waagerecht oder senkrecht auf der2D-Karte: $x_d = x_{d-1}$ oder $y_d = y_{d-1}$. An aufeinanderfolgenden Tagen wechseln sich beide Richtungen ab.

Er ist so langsam, dass Gras vor dem Ende nachwachsen kann. Am Tag $d$ gemähtes Gras erscheint am Tag $d + T$ wieder. Kreuzt er einen mindestens $T$ Tage zuvor gemähten Weg, mäht er denselben Punkt erneut. Um seine schlechte Strategie zu verbessern, möchte er solche Fälle zählen.

Zähle Kreuzungen mit früheren Strecken, auf denen das Gras nachgewachsen ist. Zähle nur „senkrechte“ Kreuzungen: ein gemeinsamer Punkt einer waagerechten und senkrechten Strecke, der Endpunkt von keiner ist.

Eingabe

Die erste Zeile enthält $N$ ($2 \leq N \leq 100,000$) und $T$ ($1 \leq T \leq N$, $T$ gerade).

Die nächsten $N$ Zeilen beschreiben die Mäherpositionen an Tagen $1 \ldots N$. Zeile $i$ enthält ganze Zahlen $x_i$ und $y_i$, nichtnegativ und höchstens $1,000,000,000$.

Ausgabe

Gib die Anzahl beschriebener Kreuzungen aus, bei denen FJ zuvor gemähtes und nachgewachsenes Gras erneut mäht.

Beispiele

Eingabe 1

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

Ausgabe 1

1

Hinweis

Am Tag7 kreuzt er eine am Tag2 gemähte Strecke; dies zählt. Die anderen Kreuzungen zählen nicht.

Hinweis: Erweiterte Grenzen von5 Sekunden pro Testfall (10 für Python und Java) und512 MB Speicher.

Aufgabenautoren: Chad Waters und Brian Dean