Problem Description

Kevin is developing his professional network in a community. Unfortunately, as an outsider, he doesn't know anyone in the community yet. However, he can establish friendships with \( n \) people.

However, not many people in the community want to befriend an outsider. Each of the \( n \) people Kevin wants to befriend has similar but different criteria for befriending outsiders. The \( i \)-th person is willing to befriend Kevin after Kevin has directly befriended \( a_i \) people in the community; otherwise, Kevin has to pay a cost of \( b_i \) to befriend the \( i \)-th person.

Your task is to ensure that Kevin befriends all \( n \) people while minimizing the cost he pays.

Input Format

The first line contains an integer \( n \).

The next \( n \) lines each contain two integers \( a_i \) and \( b_i \).

Output Format

Output a single integer, which is the minimum cost Kevin pays.

Sample Input and Output

Sample Input #1

4
3 3
1 2
0 5
3 4

Sample Output #1

3

Sample Input #2

5
0 9
1 8
2 7
3 6
4 5

Sample Output #2

0

Sample Input #3

3
0 6
2 7
3 8

Sample Output #3

8

Notes/Hints

Sample Explanation

For Sample 1: Kevin can immediately befriend the 3rd person. Since he has this friendship, he can also befriend the 2nd person. He needs to pay a cost of 3 to befriend the 1st person, giving him a total of 3 friends, which allows him to befriend the 4th person.

For Sample 2: Kevin can befriend everyone without paying any cost.

For Sample 3: Kevin should immediately befriend the 1st person, then pay a cost of 8 to befriend the 3rd person, and finally establish a friendship with the 2nd person.

Data Range and Constraints

This problem uses multiple test cases bundled together, with a total of 4 subtasks.

• 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 test cases, it is guaranteed that \( 1 \le n \le 2 \times 10^5 \), \( 1 \le i \le n \), \( 0 \le a_i \le n \), \( 0 \le b_i \le 10^4 \).

Source: CCO 2017 Day2 "Professional Network".

Note: Translation from LOJ.

见题面 Input 部分

见题面 Output 部分