\(N\) con bò của Farmer John (\(3 \leq N \leq 50\,000\)) đều đứng tại các vị trí phân biệt trên cánh đồng hai chiều của ông. FJ muốn bao quanh tất cả đàn bò bằng một hàng rào hình chữ nhật có các cạnh song song với trục \(x\) và trục \(y\), đồng thời muốn hàng rào này nhỏ nhất có thể nhưng vẫn chứa mọi con bò (bò được phép đứng trên biên).

Không may, FJ đang có ngân sách eo hẹp vì sản lượng sữa thấp trong quý trước. Do đó, ông muốn bao quanh một diện tích nhỏ hơn để giảm chi phí bảo trì, và cách duy nhất ông nghĩ ra để làm điều này là xây hai khu vực có hàng rào thay vì một. Hãy giúp ông tính tổng diện tích cần bao quanh giảm được bao nhiêu khi sử dụng hai khu vực có hàng rào thay vì một. Giống như khu vực ban đầu, hai khu vực này phải cùng nhau chứa tất cả đàn bò (bò được phép đứng trên biên), và các cạnh của chúng phải song song với trục \(x\) và trục \(y\). Hai khu vực không được phép chồng lấn, kể cả trên đường biên. Lưu ý rằng khu vực có diện tích bằng không là hợp lệ, chẳng hạn nếu một khu vực có chiều rộng bằng không và/hoặc chiều cao bằng không.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên xác định vị trí của một con bò. Tọa độ của bò là các số nguyên dương trong khoảng \(1 \ldots 1\,000\,000\,000\).

Dữ liệu ra

In một số nguyên duy nhất biểu thị tổng diện tích FJ có thể tiết kiệm được khi sử dụng hai khu vực có hàng rào thay vì một.

Ví dụ

6
4 2
8 10
1 1
9 12
14 7
2 3

107

Nguồn

USACO 2016 US Open Contest, Gold - Splitting the Field: https://usaco.org/index.php?page=viewproblem2&cpid=645

Tác giả: Brian Dean.