Cvenk

Μια ομάδα Τσέχων τουριστών περπατά σε έναν λαβύρινθο με παράξενο ,όμοιο με τον εαυτό του, σχήμα. Η κάτοψη του λαβυρίνθου είναι ένα τρίγωνο Sierpinski - μια δομή φράκταλ που πήρε το όνομά του από τον Πολωνό μαθηματικό Waclaw Sierpiński.
Ο λαβύρινθος αποτελείται από ένα δισεκατομμύριο σειρές αριθμημένες από το ~0~ έως το ~10^9-1~ από πάνω προς τα κάτω και ένα δισεκατομμύριο στήλες αριθμημένες από το ~0~ έως το ~10^9-1~ από αριστερά προς τα δεξιά. Τα πεδία στον λαβύρινθο μπορεί να είναι είτε ελεύθερα είτε μπλοκαρισμένα.
Το πεδίο στη σειρά ~X~ και στη στήλη ~Y~ είναι ελεύθερο εάν το αποτέλεσμα της λειτουργίας "και" στα bit στους αριθμούς ~X~ και ~Y~ ισούται με μηδέν, διαφορετικά μπλοκάρεται. Με άλλα λόγια, ένα πεδίο μπλοκάρεται εάν, όταν γίνει εναλλαγή των ~X~ και ~Y~ σε δυαδικό, υπάρχει ένας ακέραιος ~k~ τέτοιος ώστε το ~k~-οστο ψηφίο από τα δεξιά του αριθμού ~X~ και το ~k~-οστο ψηφίο από τα δεξιά του αριθμού \(Υ\) είναι ίσα με ~1~.

Οι πρώτες ~32~ σειρές και στήλες του λαβύρινθου. Τα μπλοκαρισμένα πεδία είναι χρωματισμένα μαύρα Οι Τσέχοι τουρίστες είναι κουρασμένοι από μια κουραστική μέρα περιπλάνησης και θα ήθελαν να συναντηθούν σε ένα ελεύθερο πεδίο και να ανταλλάξουν εμπειρίες. Σε κάθε βήμα, ένας τουρίστας μπορεί να μεταπηδήσει σε ένα από τα διπλανά ελεύθερα πεδία (πάνω, κάτω, αριστερά ή δεξιά).
Γράψτε ένα πρόγραμμα που, με βάση τις τρέχουσες τοποθεσίες των τουριστών, που θα καθορίζει τον ελάχιστο συνολικό αριθμό βημάτων που απαιτούνται για να συναντηθούν όλοι οι τουρίστες στο ίδιο πεδίο.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N~ - τον αριθμό των τουριστών. Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους ~R_i~ και ~S_i~ – η γραμμή και η στήλη του πεδίου όπου βρίσκεται ο ~i~-οστός τουρίστας.
Όλοι οι τουρίστες βρίσκονται σε ελεύθερα πεδία και είναι πιθανό να υπάρχουν πολλοί τουρίστες στο ίδιο πεδίο.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο ελάχιστο αριθμό βημάτων.
Σημείωση: Συνιστούμε να χρησιμοποιήσετε έναν ακέραιο τύπο δεδομένων 64 bit (int64 σε Pascal, long long σε C/C++).

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	17	~N=2~ ~0\le R_K, S_K< 10^9~
2	21	~2\le N \le 100~ ~0 \le R_K, S_K< 10^9~
3	22	~ 2 \le N \le 10^5~ ~1 \le R_K,S_K < 500~
4	40	~ 2 \le N \le 10^5~ ~0\le R_K, S_K < 10^9~

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

input

2
2 1
4 3

output

6

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

Ένα από τα πεδία όπου οι γενναίοι Τσέχοι τουρίστες θα μπορούσαν να συναντηθούν είναι το ~(2,\,0)~.

---

input

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

output

50

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

Ένα από τα πεδία όπου οι παιχνιδιάρικοι Τσέχοι τουρίστες θα μπορούσαν να συναντηθούν είνα ~(8,\,4)~.

---