Farmer John khá đáng tin cậy trong mọi khía cạnh quản lý trang trại, ngoại trừ một điều: ông cực kỳ tệ trong việc cắt cỏ đúng lúc. Thực tế, mỗi ngày ông chỉ xoay xở di chuyển được máy cắt cỏ một lần. Vào ngày 1, ông bắt đầu tại vị trí \((x_1,y_1)\); vào ngày \(d\), ông cắt cỏ dọc theo một đoạn thẳng đến vị trí \((x_d,y_d)\), di chuyển theo chiều ngang hoặc chiều dọc trên bản đồ hai chiều của trang trại; nghĩa là \(x_d=x_{d-1}\) hoặc \(y_d=y_{d-1}\). FJ luân phiên giữa chuyển động ngang và dọc trong những ngày liên tiếp.

FJ tiến triển chậm đến mức một phần cỏ ông đã cắt có thể mọc lại trước khi ông hoàn tất toàn bộ công việc. Bất kỳ phần cỏ nào được cắt vào ngày \(d\) sẽ mọc lại vào ngày \(d+T\), nên nếu đường cắt của FJ giao với một đường ông đã cắt ít nhất \(T\) ngày trước, ông sẽ cắt cỏ tại cùng một điểm thêm lần nữa. Trong nỗ lực sửa đổi chiến lược cắt cỏ tồi tệ của mình, FJ muốn đếm số lần điều này xảy ra.

Hãy đếm số lần đường cắt của FJ giao với một đoạn trước đó mà cỏ trên đó đã mọc lại. Bạn chỉ được tính các giao điểm "vuông góc", được định nghĩa là điểm chung của một đoạn ngang và một đoạn dọc nhưng không phải đầu mút của bất kỳ đoạn nào trong hai đoạn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(2\le N\le100\,000\)) và \(T\) (\(1\le T\le N\), \(T\) chẵn).

\(N\) dòng tiếp theo mô tả vị trí của máy cắt cỏ vào các ngày \(1\ldots N\). Dòng thứ \(i\) trong số này chứa hai số nguyên \(x_i\) và \(y_i\) (các số nguyên không âm, mỗi số không vượt quá \(1\,000\,000\,000\)).

Dữ liệu ra

In số giao điểm được mô tả ở trên, nơi FJ cắt lại một điểm cỏ đã mọc lại sau lần cắt trước.

Ví dụ

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

1

Lưu ý: Bài này có giới hạn được mở rộng: 5 giây cho mỗi trường hợp kiểm thử (10 giây đối với Python và Java) và 512 MB bộ nhớ.

Nguồn

USACO 2016 January Contest, Platinum - Mowing the Field: https://usaco.org/index.php?page=viewproblem2&cpid=601

Tác giả: Chad Waters và Brian Dean.