Dugovi

Σε μια μικρή πόλη που ονομάζεται Križ ζουν ~N~ άνθρωποι. Καθένας από αυτούς έχει δανειστεί κάποια χρήματα από ακριβώς έναν άλλον κάτοικο. Τώρα ήρθε η ώρα να ξεπληρώσουμε όλα τα χρέη, αλλά το πρόβλημα είναι ότι όλοι ξόδεψαν όλα τους τα χρήματά τους!

Ο ταγματάρχης του Križ αποφάσισε να λύσει αυτό το πρόβλημα. Η πόλη θα δώσει χρήματα σε λίγους ανθρώπους για να μπορέσουν να ξεπληρώσουν τα χρέη τους. Όταν κάποιοι παίρνουν τα χρήματά τους πίσω, ξεκινά μια αλυσιδωτή αντίδραση - για παράδειγμα: το άτομο ~A~ παίρνει χρήματα από την πόλη. Το άτομο ~A~ χρησιμοποιεί αυτά τα χρήματα για να πληρώσει το χρέος προς το άτομο ~B~. Το άτομο ~B~ στη συνέχεια χρησιμοποιεί αυτά τα χρήματα για να πληρώσει το χρέος προς το άτομο ~C~ κ.λπ. Εάν το άτομο ~B~ δεν είχε αρκετά χρήματα για να αποπληρώσει το χρέος, περιμένει μέχρι να πάρει αρκετά. Εάν έχει περισσότερα από αρκετά χρήματα, το άτομο ~B~ θα κρατήσει ό,τι έχει απομείνει μετά την απόσβεση.

Άλλο παράδειγμα: εάν δύο άτομα ζουν στο Križ και οφείλουν 100$ ο ένας στον άλλο, η πόλη θα δώσει 100$ σε έναν από αυτούς για να μπορέσει να επιστρέψει το χρέος στον άλλο.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N\;(2 \leq N \leq 200\,000)~, τον αριθμό των κατοίκων του Križ. Αριθμούνται από το ~1~ έως το ~N~.

Οι ακόλουθες ~N~ γραμμές περιέχουν δύο ακέραιους, χωρισμένους με κενό. Στην ~i~-οστή από αυτές τις γραμμές, ο πρώτος αριθμός - ~A_i~ αντιπροσωπεύει το αναγνωριστικό του ατόμου που το ~i~-οστό άτομο χρωστάει χρήματα στο ~(1 \leq A_i \leq N,\;A_i \neq i)~ και ο δεύτερος ~B_i~ αντιπροσωπεύει το ποσό του χρέους σε $ ~(1 \leq B_i \leq 10\,000)~.

Έξοδος

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

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

input

4
2 100
1 100
4 70
3 70

output

170

input

3
2 120
3 50
2 80

output

150

input

5
3 30
3 20
4 100
5 40
3 60

output

110