Farmer John gestisce bene la fattoria tranne che nel falciare tempestivamente. Muove il tosaerba solo una volta al giorno. Il giorno1 parte da $(x_1, y_1)$ e il giorno $d$ falcia in linea retta fino a $(x_d, y_d)$, orizzontalmente o verticalmente sulla mappa2D: $x_d = x_{d-1}$ oppure $y_d = y_{d-1}$. Alterna movimenti orizzontali e verticali in giorni consecutivi.

Avanza così lentamente che l'erba può ricrescere prima della fine. Quella tagliata il giorno $d$ riappare il giorno $d + T$. Incrociando un percorso falciato almeno $T$ giorni prima, taglia di nuovo lo stesso punto. Per migliorare la cattiva strategia vuole contare tali casi.

Conta gli incroci con segmenti precedenti su cui l'erba è ricresciuta. Conta solo incroci «perpendicolari»: punto comune fra un segmento orizzontale e uno verticale che non sia estremo di nessuno.

Input

La prima riga contiene $N$ ($2 \leq N \leq 100,000$) e $T$ ($1 \leq T \leq N$, $T$ pari).

Le successive $N$ righe descrivono le posizioni del tosaerba nei giorni $1 \ldots N$. La riga $i$ contiene interi $x_i$ e $y_i$, non negativi e al massimo $1,000,000,000$.

Output

Stampa il numero di incroci descritti, dove FJ ritaglia erba già tagliata e ricresciuta.

Esempi

Input 1

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

Output 1

1

Nota

Il giorno7 incrocia un segmento tagliato il giorno2: conta. Gli altri incroci non contano.

Nota: limiti ampliati a5 secondi per caso (10 per Python e Java) e512 MB di memoria.

Autori del problema: Chad Waters e Brian Dean