P6346 [CCO 2017] Professional Network

Kevin is building his professional network in a community. Unfortunately, he is an outsider and does not know anyone in the community yet. However, he can form friendships with $n$ people. However, not many people in the community want to be friends with an outsider. Each of the $n$ people Kevin wants to befriend has a similar but different rule for becoming friends with an outsider. After Kevin already directly knows $a_i$ people in the community, person $i$ is willing to become friends with Kevin; otherwise, Kevin must pay a cost of $b_i$ to become friends with them. Your task is to make Kevin become friends with all $n$ people while minimizing the total cost he pays.

The first line contains an integer $n$. The next $n$ lines each contain two integers $a_i, b_i$.

Output one integer on a single line, representing the minimum total cost Kevin needs to pay.

#### Sample Explanation For Sample $1$: Kevin can immediately become friends with person $3$. After establishing this friendship, he can also become friends with person $2$. He needs to pay a cost of $3$ to become friends with person $1$. Then he has $3$ friends in total, which allows him to become friends with person $4$. For Sample $2$: Kevin does not need to pay anything to become friends with everyone. For Sample $3$: Kevin should immediately become friends with person $1$, then pay a cost of $8$ to become friends with person $3$, and finally establish a friendship with person $2$. #### Constraints and Notes **This problem uses bundled multi-test evaluation, with $4$ subtasks in total.** - Subtask 1 (15 points): all $b_i$ are equal to $1$; - Subtask 2 (30 points): $1 \le n \le 10$; - Subtask 3 (30 points): $1 \le n \le 10^3$. - Subtask 4 (25 points): $1 \le n \le 2 \times 10^5$. For all testdata, it is guaranteed that $1 \le n \le 2 \times 10^5$, $1 \le i \le n$, $0 \le a_i \le n$, and $0 \le b_i \le 10^4$. Source: [CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2 “[Professional Network](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)”. Note: This translation is from [LOJ](https://loj.ac/problem/2754). Translated by ChatGPT 5