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 sends a gift to person , is the next person to send a gift (in case 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 to , and a connection from to with value indicates that person must gift person , and in case Arthur wants to change for whom must give a gift, he must pay a fee of . In this example, the least total cost to fix the game is , since Arthur can make the following changes:
- Person now gives a gift to person , and Arthur pays a fee of for that;
- Person now gives a gift to person , and Arthur pays a fee of for that;
- Person now gives a gift to person , and Arthur pays a fee of for that.
This way, Arthur pays a fee of .
Input
The first line of input contains an integer , representing the number of people in the game. The following lines have two integers each. The first number in the -th of these lines represents for whom will send a gift (in Arthur's initial random choice), and the second integer represents the fee Arthur has to pay to person 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
Subtask 1 (10 points)
In Arthur's initial choices, everyone will receive a gift from someone.
Subtask 2 (20 points)
Subtask 3 (20 points)
In Arthur's initial choices, there is only one person 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 . In other words, the graph formed is a tree (if we ignore the direction of edges and the self-loop from ).
Subtask 4 (30 points)
Every fee is equal to .
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
Comments