Professional Network

Ο Κέβιν αναπτύσσει το επαγγελματικό του δίκτυο σε μια συγκεκριμένη κοινότητα. Δυστυχώς, δεν έχει συνδεθεί με κανέναν ακόμα. Αλλά έχει τα μάτια του σε ~N~ δυνητικά πολύτιμες συνδέσεις, αριθμημένες από το ~1~ έως το ~N~. Είναι αποφασισμένος να συνδεθεί με όλους.

Ωστόσο, λίγοι άνθρωποι σε αυτήν την κοινότητα είναι πρόθυμοι να κάνουν φίλο έναν ξένο. Καθένας από τους ~N~ ανθρώπους με τους οποίους ο Kevin θέλει να συνδεθεί έχει παρόμοια, αλλά διαφορετικά κριτήρια για τον προσδιορισμό του ποιος είναι ξένος και ποιος δεν είναι. Το άτομο ~i~ είναι πρόθυμο να γίνει φίλος με τον Kevin αν ήδη έχει τουλάχιστον ~A_i~ συνδέσεις μέσα στην κοινότητα ή αν ο Kevin δώσει σε αυτό το άτομο ~B_i~ πόντους διαδικτύου.

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

Είσοδος

Η πρώτη γραμμή θα περιέχει τον ακέραιο ~N~ (~1 \le N \le 200\,000~). Κάθε μία από τις επόμενες ~N~ γραμμές θα περιέχει τους ακέραιους ~A_i~ και ~B_i~ (~1 \le i \le N~, ~0 \le A_i \le N~, ~0 \le B_i \le 10\,000~).

Βαθμολογία

Για ~2~ από τους ~25~ διαθέσιμους βαθμούς, ~B_i = 1~ για κάθε ~i~. Για επιπλέον ~4~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 10~. Για επιπλέον ~7~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 1\,000~.

Έξοδος

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

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

input

4
3 3
1 2
0 5
3 4

output

3

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

Ο Kevin μπορεί να συνδεθεί άμεσα με το άτομο ~3~ και με αυτή τη σύνδεση μπορεί να επίσης να συνδεθεί με το άτομο ~2~. Δεν έχει αρκετές συνδέσεις για να συνδεθεί με το άτομο ~1~ ή το άτομο ~4~, επομένως δίνει ~3~ πόντους διαδικτύου στο άτομο ~1~ για να αποκτήσει ~3~ συνδέσεις συνολικά που του επιτρέπουν να συνδεθεί με το άτομο ~4~.

input

5
0 9
1 8
2 7
3 6
4 5

output

0

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

Είναι πιθανό ο Kevin να μπορεί να συνδεθεί με όλους χωρίς να χαρίσει πόντους διαδικτύου.

input

3
0 6
2 7
3 8

output

8

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

Ο Κέβιν θα πρέπει να συνδεθεί με το άτομο ~1~ αμέσως και μετά να δώσει ~8~ πόντους διαδικτύου στο άτομο ~3~ για να συνδεθεί μαζί τους και μετά συνδεθεί με το άτομο ~2~.