cabana

Ben are un teren pe care se află o pădure cu arbori seculari. Acolo vrea să-şi construiască o cabană, însă el fiind ecologist nu vrea să taie niciun arbore, ci vrea să găsească cea mai mare suprafaţă dreptunghiulară fără arbori. El caută o suprafaţă dreptunghiulară străjuită doar în colţuri de arbori şi cu laturile paralele cu axele de coordonate. Ben cunoaşte coordonatele tuturor arborilor din pădure şi vă roagă să-l ajutaţi să găsească aria dreptunghiului cu suprafaţă maximă care are arbori doar în cele patru colțuri.

Figura 1 din enunțul original al problemei cabana.Mărește schema ↗

Cerinţă

Cunoscând numărul arborilor din pădure şi coordonatele acestora, se cere să se determine aria dreptunghiului de suprafaţă maximă cu copaci doar în cele 4 colţuri, unde Ben intenţionează să-şi construiască cabana.

Date de intrare

Fişierul de intrare cabana.in conţine pe prima linie un număr natural $n$, reprezentând numărul de arbori din pădure. Pe fiecare dintre următoarele $n$ linii se află două numere întregi, separate printr-un spațiu, ce reprezintă abscisa și ordonata unui arbore.

Date de ieşire

În fişierul de ieşire cabana.out se scrie pe prima linie numărul natural $a$, reprezentând aria dreptunghiului de suprafață maximă.

Restricţii şi precizări

• Pentru $10\%$ din teste: $1 \leq n \leq 10$ și $-10^3 \leq x,y \leq 10^3$.
• Pentru $30\%$ din teste: $1 \leq n \leq 500$ și $-10^3 \leq x,y \leq 10^3$.
• Pentru $50\%$ din teste: $1 \leq n \leq 500$ și $-10^6 \leq x,y \leq 10^6$.
• Pentru $70\%$ din teste: $1 \leq n \leq 3\ 000$ și $-10^9 \leq x,y \leq 10^9$.
• Pentru $100\%$ din teste: $1 \leq n \leq 50\ 000$ și $-10^9 \leq x,y \leq 10^9$.
• Nu există doi arbori așezați pe aceeași poziție.

Exemplu

cabana.in

22
6 25
25 22
15 5
23 23
6 7
11 16
11 20
10 22
6 16
12 6
7 19
10 19
10 14
7 14
7 7
18 14
18 7
10 7
19 19
29 19
29 4
19 4

cabana.out

150

Explicație

Coordonatele dreptunghiului de arie maximă cu laturile paralele cu axele de coordonate şi care nu conţine arbori decât în colţuri sunt $(19,19)$, $(29,19)$, $(29,4)$, $(19,4)$, deci aria maximă este $150$.