Farmer John đang dự định xây dựng \(N\) đồng cỏ hình vuông có hàng rào bao quanh trong trang trại của mình (\(2 \le N \le 50\,000\)), mỗi đồng cỏ có kích thước chính xác \(K \times K\) (\(1 \le K \le 1\,000\,000\)). Đồng cỏ thứ \(i\) có tâm tại điểm \((x_i, y_i)\) với các tọa độ nguyên trong khoảng từ \(-1\,000\,000\) đến \(1\,000\,000\). Tuy nhiên, vì vội vàng hoàn thành kế hoạch, FJ nhận ra rằng ông có thể đã vô tình đặt hai đồng cỏ ở những vị trí chồng lấn nhau (chồng lấn ở đây nghĩa là hai đồng cỏ có chung một phần diện tích dương). Không có hai đồng cỏ nào có cùng một tâm.

Cho vị trí của mỗi đồng cỏ hình vuông dự kiến, hãy giúp FJ tính diện tích chung của hai đồng cỏ chồng lấn. In ra \(0\) nếu không có hai hình vuông nào chồng lấn, và in ra \(-1\) nếu có nhiều hơn một cặp đồng cỏ chồng lấn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách. Giá trị \(K\) được đảm bảo là số chẵn.
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\), mô tả tâm của đồng cỏ thứ \(i\).

Dữ liệu ra

In ra diện tích chung của hai hình vuông chồng lấn. In ra \(0\) nếu không có hai hình vuông nào chồng lấn, và in ra \(-1\) nếu có nhiều hơn một cặp đồng cỏ chồng lấn.

Ví dụ

4 6
0 0
8 4
-2 1
0 7

20

Nguồn

USACO 2013 January Contest, Silver — Problem 2: Square Overlap

Tác giả đề: Brian Dean, 2013.