36ος ΠΔΠ Καμπ (κοινά)
meeting (meeting)

Μια ομάδα \(N\) προγραμματιστών ζεί σε μία πόλη στην οποία υπάρχουν οριζόντιοι και κάθετοι δρόμοι, σε ίση απόσταση μεταξύ τους, που σχηματίζουν ένα πλέγμα (grid). Οι δρόμοι είναι αριθμημένοι κατά σειρά με φυσικούς αριθμούς, τόσο στην οριζόντια όσο και στην κάθετη διάσταση. Κάθε προγραμματιστής ζει σε κάποια διασταύρωση αυτής της πόλης και γνωρίζουμε τις συντεταγμένες του σπιτιού του.

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

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

Δεδομένα εισόδου (meeting.in)

Η πρώτη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό \(N\), το πλήθος των προγραμματιστών. Κάθε μία από τις επόμενες \(N\) γραμμές της εισόδου περιέχει δύο αριθμούς, \(X\) και \(Y\), χωρισμένους με ένα κενό διάστημα. Αυτές είναι οι συντεταγμένες του σπιτιού στο οποίο μένει ο αντίστοιχος προγραμματιστής. Θεωρήστε ότι δε θα υπάρχουν δύο προγραμματιστές που τα σπίτια τους να έχουν τις ίδιες συντεταγμένες.

Δεδομένα εξόδου (meeting.out)

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: την ελάχιστη συνολική απόσταση που θα χρειαστεί να καλύψουν οι προγραμματιστές.

Παράδειγμα αρχείων εισόδου-εξόδου:

meeting.in	meeting.out
7 1 3 3 2 3 5 6 9 10 1 12 4 5 7	39

Εξήγηση: Αν επιλεγεί το σπίτι του τρίτου προγραμματιστή, με συντεταγμένες \((3, 5)\), η συνολική απόσταση που θα πρέπει να καλυφθεί είναι \(4 + 3 + 0 + 7 + 11 + 10 + 4 = 39\). Αυτή είναι και η ελάχιστη δυνατή.

Περιορισμοί:

\(2 \leq N \leq 1.000.000\),
Οι τιμές των συντεταγμένων δε θα είναι αρνητικές και δε θα υπερβαίνουν το \(10^7\).

Προσέξτε ότι για μεγάλες τιμές του Ν και των συντεταγμένων, μπορεί οι συνολικές αποστάσεις (καθώς και κάποια ενδιάμεσα αποτελέσματα που τυχόν χρειάζονται για τον υπολογισμό τους) να υπερβαίνουν το \(2^{32}\).

Επίσης, προσέξτε ότι το μέγεθος των δεδομένων εισόδου μπορεί να είναι μεγάλο. Σας συστήνουμε να διαβάσετε τα δεδομένα με αποδοτικό τρόπο (βλ. <cstdio> και scanf).

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 37%, θα είναι \(N \leq 10.000\).