Розділення поля#10574
Усі корів фермера Джона перебувають у різних точках його двовимірного поля. FJ хоче обгородити всіх корів прямокутною огорожею, сторони якої паралельні осям та . Він хоче, щоб огорожа була якомога меншою, але при цьому містила всіх корів; корови можуть перебувати на межі огорожі.
На жаль, через низьке виробництво молока минулого кварталу FJ зазнає фінансових труднощів. Тому він хотів би зменшити загальну площу, яку йому необхідно огородити, і єдиний спосіб, який він може придумати для цього, — побудувати дві огорожі замість однієї.
Допоможіть FJ визначити, яку загальну площу він зможе заощадити, використовуючи дві огорожі замість однієї. Як і початкова огорожа, дві нові огорожі разом мають містити всіх корів; корови можуть перебувати на їхніх межах, а сторони обох огорож мають бути паралельні осям та . Дві огорожі не повинні перетинатися, навіть своїми межами.
Зверніть увагу, що огорожі нульової площі дозволені. Наприклад, огорожа може мати нульову ширину та/або нульову висоту.
У першому рядку міститься ціле число n~(3 \le n \le 50000).
У наступних рядках містяться по два цілих числа, що задають координати однієї корови. Координати корів є додатними цілими числами в діапазоні від до 10^9.
Виведіть одне ціле число — загальну площу, яку FJ зможе заощадити, використовуючи дві огорожі замість однієї.
Приклад 1