Cắt Cỏ

Một máy cắt cỏ di chuyển trên mặt phẳng theo $N$ đoạn thẳng liên tiếp, luân phiên nằm ngang và thẳng đứng. Bạn được cho tọa độ của $N+1$ điểm (bao gồm điểm xuất phát), tạo thành $N$ đoạn (đánh số từ $0$ đến $N-1$).

Đoạn thứ $i$ và đoạn thứ $j$ ($i<j$) giao nhau vuông góc nếu:

• Một đoạn nằm ngang và đoạn kia thẳng đứng,
• Chúng thực sự cắt nhau (không chỉ chạm đầu mút),
• $j-i\ge T$.

Đếm số cặp đoạn giao nhau vuông góc thỏa mãn điều kiện trên.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $T$ (số điểm và ngưỡng khoảng cách).
• $N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x_i$, $y_i$ là tọa độ của điểm thứ $i$ (từ $0$ đến $N-1$).

Đảm bảo: Các đoạn liên tiếp luân phiên nằm ngang và thẳng đứng (tức là mỗi đoạn chỉ thay đổi đúng một tọa độ so với đoạn trước).

Dữ liệu ra

Một số nguyên duy nhất — số cặp đoạn giao nhau vuông góc với $j-i\ge T$.

Ràng buộc

• $2\le N\le {10}^5$
• $0\le x_i,y_i\le {10}^9$
• $2\le T\le N$ ($T$ là số chẵn)

Ví dụ

Ghi chú

• Hai đoạn được coi là giao nhau khi chúng cắt nhau tại một điểm nằm hoàn toàn bên trong cả hai đoạn (không phải tại đầu mút).
• $T$ luôn là số chẵn.