Farmer John quản lý trang trại đáng tin cậy mọi mặt trừ cắt cỏ đúng lúc. Ông chỉ di chuyển máy cắt một lần mỗi ngày. Ngày1 bắt đầu ở $(x_1, y_1)$, ngày $d$ cắt theo đoạn thẳng tới $(x_d, y_d)$, ngang hoặc dọc trên bản đồ2D: $x_d = x_{d-1}$ hoặc $y_d = y_{d-1}$. Các ngày liên tiếp luân phiên di chuyển ngang và dọc.

Ông chậm đến mức cỏ có thể mọc lại trước khi cắt hết. Cỏ cắt ngày $d$ trở lại ngày $d + T$. Nếu đường đi giao đường cắt ít nhất $T$ ngày trước, ông cắt lại cùng điểm. Để cải thiện chiến lược tệ, ông muốn đếm các lần này.

Đếm giao với đoạn trước mà cỏ đã mọc lại. Chỉ đếm giao «vuông góc»: điểm chung của đoạn ngang và dọc, không là đầu mút của đoạn nào.

Dữ liệu vào

Dòng đầu chứa $N$ ($2 \leq N \leq 100,000$) và $T$ ($1 \leq T \leq N$, $T$ chẵn).

$N$ dòng tiếp theo mô tả vị trí máy vào ngày $1 \ldots N$. Dòng thứ $i$ chứa số nguyên $x_i$ và $y_i$, không âm và không quá $1,000,000,000$.

Dữ liệu ra

In số giao điểm mô tả trên, nơi FJ cắt lại cỏ từng bị cắt và đã mọc lại.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

Ngày7 ông giao đoạn cắt ngày2, được đếm. Các giao khác không đếm.

Chú ý: giới hạn mở rộng5 giây mỗi test (10 cho Python và Java), bộ nhớ512 MB.

Tác giả bài toán: Chad Waters và Brian Dean