3D Histogram

Κος Malnar (από το τηλέφωνο): Ακούστε, έπρεπε να τοποθετήσω στο Ζάγκρεμπ μερικές αφίσες στη μέση της νύχτας. Έπεσα πάνω σε έναν φράχτη που ήταν φτιαγμένος από μερικές σανίδες διαφορετικού ύψους και σκεφτόμουν πώς να υπολογίσω τη μεγαλύτερη επιφάνεια μιας αφίσας που μπορώ να χωρέσω στον φράχτη. Αυτό δεν θα δημιουργούσε ένα ωραίο πρόβλημα COCI;

Συνεργάτης: Τι έκανες;! Τέλος πάντων, το πρόβλημα δεν είναι καλό. Είναι ένα τυπικό κόλπο με μονότονη ουρά, το διδάσκουμε ακόμη και σε μαθητές δημοτικού σχολείου στις κατασκηνώσεις μας.

Κος Malnar: Τι θα λέγατε να το τροποποιήσετε λίγο ζητώντας την απάντηση για κάθε πρόθημα ή κάτι τέτοιο, αυτό θα πρέπει να είναι αρκετά δύσκολο.

Συνεργάτης: Αυτό ακριβώς το πρόβλημα παρουσιάστηκε πέρυσι στον διαγωνισμό πρόκρισης CERC. Είναι δύσκολο, καταλήγει στο κόλπο των Harbingers, αλλά τώρα το έχουν δει όλοι.

Κος Malnar: Είστε σίγουρος ότι δεν μπορούμε να κάνουμε τίποτα;

Συνεργάτης: Νομίζω ότι έχουμε εξαντλήσει όλα τα προβλήματα με τα ιστογράμματα. COCI 2010/2011 (Tabovi), COCI 2015/2016 (Poplava), COCI 2017/2018 (Krov), τεστ επιλογής IOI 2018 (Histogram)... Καταλαβαίνετε.

Κος Malnar: Τι γίνεται αν το ιστόγραμμα είναι τρισδιάστατο;

Συνεργάτης: Χμμ...

Σας δίνεται ένα τρισδιάστατο ιστόγραμμα, που αποτελείται από n παραλληλεπίπεδα τα οποία είναι τοποθετημένα το ένα δίπλα στο άλλο. Το i-οστό παραλληλεπίπεδο έχει πλάτος 1 μέτρο, ύψος ~a_i~ μέτρα και μήκος δύο μέτρα. Με άλλα λόγια, από μπροστά μοιάζει με ιστόγραμμα ράβδων ύψους ~a_1,\;a_2,\;\ldots,\;a_n~ και από πάνω μοιάζει με ιστόγραμμα ράβδων ύψους ~b_1,\;b_2,\;\ldots,\;b_n~.

Προσδιορίστε το παραλληλεπίπεδο με τον μέγιστο όγκο που μπορεί να τοποθετηθεί μέσα στο δεδομένο τρισδιάστατο ιστόγραμμα. Οι πλευρές αυτού του παραλληλεπιπέδου πρέπει να είναι παράλληλες με τις πλευρές των παραλληλεπιπέδων που συνθέτουν το τρισδιάστατο ιστόγραμμα.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~n~.

Η i-οστή από τις ακόλουθες ~n~ γραμμές περιέχει τους ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \le a_i, b_i \le 10^6)~.

Έξοδος

Εκτυπώστε τον όγκο σε κυβικά μέτρα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le n \le 2000~
2	90	~1 \le n \le 200\,000~

Παραδείγματα

input

5
5 3
4 4
2 1
3 2
1 5

output

24

Επεξήγηση του 1ου παραδείγματος:

Το παρακάτω σχήμα δείχνει το τρισδιάστατο ιστόγραμμα από το πρώτο παράδειγμα. Το μεγαλύτερο μπλοκ αποκτάται χρησιμοποιώντας τμήματα των δύο πρώτων μπλοκ και έχει πλάτος 2 μέτρα, ύψος 4 μέτρα και μήκος 3 μέτρα. Ο όγκος του μπλοκ είναι ~2 \cdot 4 \cdot 3 = 24~ κυβικά μέτρα.

input

6
3 1
2 1
2 2
2 3
1 1
2 2

output

8

input

5
15 19
5 6
1 13
3 7
1 2

output

285