Description

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.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $a_i, b_i$.

Output Format

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

4
3 3
1 2
0 5
3 4

3

5
0 9
1 8
2 7
3 6
4 5

0

3
0 6
2 7
3 8

8

Hint

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 Day2 “Professional Network”.

Note: This translation is from LOJ.

Translated by ChatGPT 5