The company where Arthur works organizes a secret Santa every year, and unfortunately, he is responsible for organizing the game this year. In this game, every person has to send a gift to someone previously chosen at random, and on the day of the gifts exchange, when person $A$ sends a gift to person $B$, $B$ is the next person to send a gift (in case $B$ hasn't sent it yet). When the next person to send a gift isn't defined (at the start of the game, for example), this person is chosen at random.

Since Arthur is a very distracted boy, when he randomly chose for whom each person will send a gift, he forgot that everybody must receive a gift. He also forgot to make sure that the first person to send a gift must be the last one to receive somebody's gift, due to the company's tradition. Now he has to reorganize the game. However, since his coworkers got mad with Arthur's mindlessness, they will charge a fee for Arthur to change the person they must give the gift to. Help Arthur by calculating the smallest total fee (sum of all fees) he must pay to fix the game and not get fired. For a better understanding, let's analyze the following scenario:

In the picture above, the people at the company are represented with numbers from $1$ to $9$, and a connection from $A$ to $B$ with value $C$ indicates that person $A$ must gift person $B$, and in case Arthur wants to change for whom $A$ must give a gift, he must pay a fee of $C$. In this example, the least total cost to fix the game is $23$, since Arthur can make the following changes:

• Person $8$ now gives a gift to person $6$, and Arthur pays a fee of $2$ for that;
• Person $4$ now gives a gift to person $9$, and Arthur pays a fee of $10$ for that;
• Person $1$ now gives a gift to person $7$, and Arthur pays a fee of $11$ for that.

This way, Arthur pays a fee of $2+10+11=23$.

Input

The first line of input contains an integer $N$, representing the number of people in the game. The following $N$ lines have two integers each. The first number in the $i$-th of these lines represents for whom $i$ will send a gift (in Arthur's initial random choice), and the second integer represents the fee Arthur has to pay to person $i$ to change the person that receives his or her gift.

Output

Print the least total fee Arthur has to pay to fix the game.

Constraints

$1\le N\le {10}^5$

$1\le fee\le {10}^9$

Subtask 1 (10 points)

In Arthur's initial choices, everyone will receive a gift from someone.

Subtask 2 (20 points)

$1\le N\le 15$

Subtask 3 (20 points)

In Arthur's initial choices, there is only one person $V$ that will send a gift to him or herself, and for all other people, if they send their gift, after some rounds they would eventually reach $V$. In other words, the graph formed is a tree (if we ignore the direction of edges and the self-loop from $V$).

Subtask 4 (30 points)

Every fee is equal to $1$.

Subtask 5 (20 points)

No more constraints.

Sample Input 1

9
2 11
3 20
1 20
3 10
2 10
5 4
4 1
9 2
8 3

Sample Output 1

23

Sample Input 2

3
1 4
1 3
1 3

Sample Output 2

7

Sample Input 3

9
3 5
4 4
5 6
2 1
1 2
2 2
4 4
5 5
3 4

Sample Output 3

15