Trí rất thích thú với trò chơi Age of Empires phiên bản V. Trí vừa điều khiển binh đội của mình chiếm được vùng đất Byteland. Vùng Byteland gồm có \(N\) nhà dân, ngôi nhà thứ \(i\) có tọa độ \((x_i, y_i)\) (ta hình dung lược đồ Byteland nhìn từ trên không có thể được biểu diễn trên mặt phẳng tọa độ \(\text{Oxy}\)). Trí muốn chia Byteland thành những quận nhỏ hơn để dễ cai trị, anh ấy nhờ bạn viết chương trình giúp anh ấy "chia để trị" theo các ràng buộc sau đây:

• Mỗi quận sẽ bao chứa toàn bộ các nhà dân nằm trong một đoạn tọa độ \(x\) nhất định. (Nói cách khác, ta sẽ "chia" quận theo trục hoành)
• Mỗi nhà dân chỉ nằm trong đúng một quận.
• Số lượng quận không được vượt quá \(K\).

Ngoài ra, Trí cũng muốn việc quy hoạch đảm bảo độ chia rẽ lớn nhất của các quận phải nhỏ nhất có thể. Độ chia rẽ của một quận được tính bằng khoảng cách Euclid xa nhất giữa hai nhà dân trong quận đó.

Input

Dòng đầu chứa hai số nguyên dương \(N\) và \(K\).

Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên không âm \(x_i\), \(y_i\). Dữ liệu đảm bảo không tồn tại \(i\ne j\) mà \(x_i=x_j\) và \(y_i=y_j\).

Output

Xác định độ chia rẽ \(M\) lớn nhất trong số các quận. Tuy nhiên, bạn đừng in ra \(M\) mà hãy in ra giá trị \(M^2\) (để đảm bảo kết quả luôn là số nguyên).

Ví dụ

Sample input 1

4 2
101 100
2 5
100 101
4 3

Sample output 1

8

Sample input 2

4 4
3 1
4 1
5 1
9 2

Sample output 2

0

Ràng buộc

Trong tất cả các test:

• \(1\leq K\leq N \leq 250000\)
• \(0\leq x_i, y_i\leq 10^9\).

Subtasks

• Subtask 1: \(N\leq 500\).
• Subtask 2: \(N\leq 5000\).
• Subtask 3: Không có ràng buộc gì thêm.