Farmer John은 농장 관리의 모든 면에서 믿음직하지만 제때 잔디 깎기만 못합니다. 실제로 하루에 한 번만 잔디깎이를 움직입니다.1일에 $(x_1, y_1)$에서 시작해 $d$일에 직선 구간을 따라 $(x_d, y_d)$로 가며2차원 지도에서 수평 또는 수직으로 움직입니다. 즉 $x_d = x_{d-1}$ 또는 $y_d = y_{d-1}$입니다. 연속된 날의 이동은 수평과 수직을 번갈아 합니다.

너무 느려 다 깎기 전에 일부 잔디가 다시 자랄 수 있습니다. $d$일에 깎은 잔디는 $d + T$일에 돌아오므로 적어도 $T$일 전에 깎은 경로와 만나면 같은 점을 다시 깎습니다. 나쁜 전략을 개선하려고 이런 횟수를 세려 합니다.

이미 잔디가 다시 자란 이전 구간과 경로가 교차하는 횟수를 세세요. ‘수직’ 교차만 세는데, 수평과 수직 구간의 공통점이며 어느 구간의 끝점도 아닌 점입니다.

입력

첫 줄에는 $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$ 이하의 음이 아닌 정수입니다.

출력

앞서 깎은 후 다시 자란 잔디를 재차 깎는 위 교점 수를 출력하세요.

예제

입력 1

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

출력 1

1

참고

7일에2일에 깎은 구간을 교차하며 이것은 셉니다. 다른 교차는 세지 않습니다.

설명: 제한을 늘려 테스트별5초(Python과 Java는10초), 메모리512 MB입니다.

문제 작성: Chad Waters와 Brian Dean