Tổ chức tiệc

Nhóm bạn thân của Minh gồm \(n\) người. Mỗi người trong nhóm sống tại một địa điểm khác nhau trong thành phố, được biểu diễn dưới dạng hệ tọa độ \(O(x, y)\). Người bạn thứ \(i\) sống tại tọa độ \((x[i], y[i])\).

Nhân dịp sinh nhật Minh, nhóm quyết định tổ chức một buổi tiệc tụ họp tại một địa điểm bất kì trong thành phố. Để đảm bảo mọi người có thể dễ dàng di chuyển, cả nhóm muốn chọn vị trí sao cho tổng khoảng cách cần phải di chuyển từ nhà của mọi người đến điểm đó là nhỏ nhất.

Khoảng cách giữa hai điểm \((x_1, y_1)\) và \((x_2, y_2)\) được tính theo công thức:

Bạn hãy tìm ra vị trí thỏa mãn mong muốn trên nhé.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^5)\), số lượng bạn bè.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x[i]\), \(y[i]\) \((0 \le x[i], y[i] \leq 10^9)\), biểu diễn tọa độ của người bạn thứ \(i\).

Output

In ra tổng khoảng cách nhỏ nhất mà mọi người cần di chuyển để cùng đến được một điểm bất kì.

Example

3
3 2
2 2
1 0

4

Scoring

• Có \(30\%\) số test ứng với \(n, x[i], y[i] \le 100\)
• Có \(20\%\) số test ứng với \(x[i], y[i] \le 1000\)
• \(50\%\) số test còn lại không có ràng buộc gì thêm.