Cover

Σας δίνονται N σημεία στο σύστημα συντεταγμένων. Πρέπει να καλυφθούν με ένα ή περισσότερα ορθογώνια, έτσι ώστε να πληρούνται οι ακόλουθες προϋποθέσεις:
●Οι πλευρές κάθε ορθογωνίου είναι παράλληλες με τους άξονες συντεταγμένων,
●Το κέντρο κάθε ορθογωνίου βρίσκεται στην αρχή, δηλαδή στο σημείο (0, 0),
●Κάθε δεδομένο σημείο βρίσκεται είτε στο εσωτερικό του ορθογωνίου είτε στα όριά του.

Φυσικά, είναι δυνατόν να καλύψουμε όλα τα σημεία χρησιμοποιώντας μόνο ένα ορθογώνιο, αλλά αυτό το ορθογώνιο θα μπορούσε να έχει πολύ μεγάλη επιφάνεια. Στόχος μας είναι να βρούμε μια επιλογή από τα απαιτούμενα ορθογώνια τέτοια ώστε το άθροισμα των επιφανειών τους να είναι ελάχιστο.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τον ακέραιο αριθμό ​N​ (1 ≤ N ≤ 5.000), τον αριθμό των σημείων. Κάθε μία από τις ακόλουθες N γραμμές περιέχει δύο ακέραιους αριθμούς X και Y (-50.000.000 ≤ ​X, Y ≤ 50.000.000, ​XY​ ≠ 0), τις συντεταγμένες κάθε σημείου.

Έξοδος

Πρέπει να εξάγετε το απαιτούμενο ελάχιστο άθροισμα των επιφανειών των ορθογωνίων.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 40% των συνολικών πόντων, θα κρατήσει ​N ≤ 20.

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

input

2
1 1
-1 -1

output

4

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

Επιλέγουμε το παραλληλόγραμμο του οποίου οι αντίθετες γωνίες είναι τα δεδομένα σημεία, αφού πληρεί τις προϋποθέσεις από την εργασία.

input

3
-7 19
9 -30
25 10

output

2080

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

Επιλέγουμε δύο ορθογώνια με το κέντρο τους στην αρχή των αξόνων. Το πρώτο είναι διαστάσεων 50 x 20 και καλύπτει το σημείο (25, 10). Το δεύτερο είναι διαστάσεων 18 x 60 και καλύπτει τα δύο πρώτα σημεία. Αν θέλαμε να καλύψουμε όλα τα σημεία χρησιμοποιώντας ένα ορθογώνιο, αυτό θα είχε διαστάσεις 50 x 60.

input

6
1 20
3 17
5 15
8 12
9 11
10 10

output

760