Farmer John надёжен во всём управлении фермой, кроме своевременного покоса. Он передвигает косилку лишь раз в день. В день1 начинает в $(x_1, y_1)$, в день $d$ косит по прямому отрезку до $(x_d, y_d)$, двигаясь горизонтально или вертикально на двумерной карте: $x_d = x_{d-1}$ либо $y_d = y_{d-1}$. Направления чередуются по дням.

Он так медленен, что часть травы может отрасти до завершения покоса. Трава, скошенная в день $d$, появляется в день $d + T$. Если путь пересекает путь, скошенный хотя бы $T$ дней назад, он снова косит ту же точку. Для улучшения плохой стратегии FJ хочет посчитать такие случаи.

Посчитайте пересечения пути с прежними отрезками, где трава уже отросла. Учитывайте лишь «перпендикулярные» пересечения: общую точку горизонтального и вертикального отрезков, не являющуюся концом ни одного.

Входные данные

Первая строка содержит $N$ ($2 \leq N \leq 100,000$) и $T$ ($1 \leq T \leq N$, $T$ чётно).

Следующие $N$ строк описывают позиции косилки в дни $1 \ldots N$. Строка $i$ содержит целые $x_i$ и $y_i$, оба неотрицательны и не больше $1,000,000,000$.

Выходные данные

Выведите число описанных пересечений, где FJ повторно косит ранее скошенную и отросшую траву.

Примеры

Входные данные 1

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

Выходные данные 1

1

Примечание

В день7 FJ пересекает отрезок, скошенный в день2; он учитывается. Другие пересечения не учитываются.

Примечание: ограничения расширены до5 секунд на тест (10 для Python и Java) и512 MB памяти.

Авторы задачи: Chad Waters и Brian Dean