KOVID-21

Dịch bệnh KOVID-21 đang lan rộng khắp thế giới. Cuộc sống của mọi người bị ảnh hưởng nặng nề bởi KOVID-21, nhất là những người thích đi du lịch khắp nơi.

May mắn thay, vắc-xin Hoderna sắp ra đời. Hoderna mạnh đến mức người đã tiêm Hoderna sẽ hoàn toàn không bị nhiễm KOVID-21. Nhưng Hoderna rất khó bảo quản. Để thuận tiện, chính phủ muốn chọn đúng một địa điểm làm trạm tiêm chủng. Chọn vị trí trạm tiêm là một bài toán khó: nếu trạm ở quá xa một người nào đó, người đó sẽ phàn nàn với chính phủ.

Đất nước là một mặt phẳng hai chiều với $n$ người dân. Người thứ $i$ sống tại điểm $(x_i,y_i)$; các tọa độ $x_i,y_i$ đều là số nguyên. Trong một đơn vị thời gian, người ở vị trí $(x,y)$ có thể đi tới một trong tám vị trí $(x-1,y-1)$, $(x-1,y)$, $(x-1,y+1)$, $(x,y-1)$, $(x,y+1)$, $(x+1,y-1)$, $(x+1,y)$, $(x+1,y+1)$. Độ phiền lòng của một người dân là số đơn vị thời gian người đó cần để đi từ nhà tới trạm tiêm. Hãy giúp chính phủ đặt trạm tiêm sao cho tổng độ phiền lòng của tất cả người dân là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$, số người dân.
• Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $x_i,y_i$ cách nhau bởi dấu cách: vị trí nhà của người thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng độ phiền lòng nhỏ nhất của tất cả người dân.

Ràng buộc

• $1\le n\le {10}^6$.
• $-{10}^9\le x_i,y_i\le {10}^9$.

Ví dụ