Putnam

Μετά τις σπουδαίες επιδόσεις σας σε διαγωνισμούς πληροφορικής, εισαχθήκατε στο Πανεπιστήμιο του Βατερλώ. Στο πρώτη σας εξάμηνο εκεί, γεμάτοι ενθουσιασμό, και θέλοντας να αυξήσετε το σερί επιτυχιών σας σε ακαδημαϊκούς διαγωνισμούς, αποφασίζετε να λάβετε μέρος στον διαγωνισμό Putnam.

Τρεις μήνες αργότερα, μαθαίνεται τη βαθμολογία σας. Είναι πολύ καλή, οπότε αποφασίζετε να το προσθέσετε στο βιογραφικό σας. Ωστόσο, τα δημοσιευμένα αποτελέσματα περιλαμβάνουν μόνο τη μέση κατάταξη για κάθε μία από τις βαθμολογίες που επιτεύχθηκε. Πιστεύετε ότι αυτές μπορεί να μην είναι αρκετές πληροφορίες και θέλετε να συμπεριλάβετε το ακριβές εύρος στο οποίο βρίσκετε η βαθμολογία σας (δηλαδή εάν υπάρχουν ~25~ άτομα με βαθμολογίες καλύτερες από τις δικές σας και ~3~ άτομα ισοβαθμούν μαζί σας, το εύρος θα ήταν ~26 - 29~).

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

Είσοδος

Η πρώτη γραμμή της αρχείου εισόδου θα περιέχει έναν ακέραιο ~N~ μεταξύ του ~1~ και του ~100\,000~ (κλειστό διάστημα).

Θα ακολουθούν ~N~ γραμμές, που θα περιέχουν τις βαθμολογίες που επιτεύχθηκαν στον διαγωνισμό, καθώς και τη μέση κατάταξη για κάθε έναν από αυτούς. Καθεμία από αυτές τις γραμμές θα περιέχει δύο αριθμούς, χωρισμένους με ένα κενό. Ο πρώτος αριθμός θα είναι μεταξύ του ~0~ και του ~3 * 10^9~ (κλειστό διάστημα). Θα αντιστοιχεί σε μία βαθμολογία που επιτεύχθηκε στον διαγωνισμό από κάποια άτομα. Ο δεύτερος αριθμός θα είναι ένας δεκαδικός αριθμός μεταξύ του ~0~ και του ~3 * 10^8~ που θα καθορίζεται χρησιμοποιώντας τη μορφή της εισόδου του παραδείγματος και θα περιέχει τη μέση κατάταξη που αντιστοιχεί σε εκείνη τη βαθμολογία.

Η τελευταία γραμμή της εισόδου περιέχει τη βαθμολογία σας στο διαγωνισμό. Μπορείτε να υποθέσετε ότι αυτός ο αριθμός φαίνεται ως ο πρώτος αριθμός σε μία από τις προηγούμενες ~N~ γραμμές.

Έξοδος

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

Παράδειγμα

input

6
5 2
4 10
3 20.5
1 34
0 35
2 29
4

output

4
16