Πολύγωνο Κουτιών

Η προσπάθεια του Τάκη να φτιάξει όμοιες πίτσες απέτυχε παταγωδώς! Για να μπορέσει να ξεχαστεί, ο Τάκης αποφάσισε να παίξει με μερικά κουτιά πίτσας. Συγκεκριμένα, έχει αγοράσει ~N~ κουτιά σε σχήμα ορθογωνίου παραλληλογράμμου. Το ~i~-οστό κουτί έχει πλάτος ~w_i~ και ύψος ~h_i~.

Αρχικά, ο Τάκης έβαλε το πρώτο κουτί στο πάτωμα, έπειτα έβαλε το δεύτερο κουτί από πάνω του, και ούτω καθεξής, δημιουργώντας έναν πύργο. Τα κουτιά τοποθετήθηκαν με προσανατολισμό τέτοιον ώστε οι πλευρές με μήκος ~w_i~ να είναι παράλληλες προς το έδαφος. Επιπλέον, επειδή ο Τάκης είναι τελειομανής, φρόντισε ο πύργος του να έχει κατακόρυφο άξονα συμμετρίας, όπως φαίνεται στο ακόλουθο σχέδιο.

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

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο polybox.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο polybox.out.

Αρχεία εισόδου (polybox.in)

Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό ~N~: το πλήθος των κουτιών. Ακολουθούν ~N~ γραμμές, καθεμία από τις οποίες περιέχει δύο ακέραιους αριθμούς ~w_i~ και ~h_i~, χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλάτος και το ύψος του ~i~-οστού κουτιού. Τα κουτιά δίνονται με τη σειρά που τοποθετούνται στον πύργο του Τάκη, από κάτω προς τα πάνω.

Αρχεία εξόδου (polybox.out)

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την περίμετρο του σχήματος που δημιουργήθηκε.

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

Είσοδος:

3
3
6 1
4 2
9 1

Έξοδος:

30

Εξήγηση: Το παράδειγμα αντιστοιχεί στο παραπάνω σχέδιο. Το κάτω κουτί έχει πλάτος ~6~ και ύψος ~1~, το μεσαίο έχει πλάτος ~4~ και ύψος ~2~ και το επάνω έχει πλάτος ~9~ και ύψος ~1~. Μπορεί κανείς να υπολογίσει, και με την βοήθεια του σχεδίου, ότι η περίμετρος αυτού του σχήματος ισούται με ~30~.

Περιορισμοί

• ~1 \le N \le 100.000~
• ~1 \le w_i, h_i \le 10^{40}~

Υποπροβλήματα:

1. (5 βαθμοί) ~w_1 = w_2 = ... = w_N~ (όλα τα πλάτη είναι ίσα), ~w_i \le 10^9~ και ~h_i \le 10^9~
2. (25 βαθμοί) ~N \le 2~, ~w_i \le 10^9~ και ~h_i \le 10^9~
3. (60 βαθμοί) ~w_i \le 10^9~ και ~h_i \le 10^9~
4. (10 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί

Παρατηρήσεις

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~2~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~128~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: polybox *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: polybox */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: polybox */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: polybox */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.