Rezolvare PBinfo #2728

Uitându-ne din New Jersey către New York, Manhattan, departe, în zare, se văd zgârie norii. De la distanță, nu distingem clădirile, ci numai o linie formată din segmente orizontale și verticale, așa numita skyline.

Cerința

Determinați care este aria celui mai mare dreptunghi care se poate înscrie în skyline.

Date de intrare

Prima linie a fișierului skyline.in va conține numărul n de segmente orizontale din linie. Pe următoarele n linii vor fi trecute perechi de numere h l, reprezentând înălțimea și lungimea fiecărui segment.

Date de ieșire

Fișierul de ieșire skyline.out va conține un singur număr, aria celui mai mare dreptunghi conținut în skyine.

Restricții și precizări

• 1 ≤ n ≤ 40.000;
• 0 ≤ h ≤ 2.000.000.000;
• 1 ≤ l ≤ 50.000;
• Dreptunghiul maximal are laturile verticale şi orizontale.

Exemplu:

skyline.in

7
4 3
11 6
8 2
9 4
2 2
4 9
8 9

skyline.out

96

Explicație

Cel mai mare dreptunghi care se poate înscrie începe la coordonatele (3, 0) şi are laturile de lungime 12 şi 8.