The Knights of Kingdom Z are a powerful organization, gathering elites from all over. They rob the rich to help the poor and punish evil to promote good, earning praise from all sectors of society.

Recently, a terrible event occurred: the evil Kingdom Y launched a war of aggression against Kingdom Z. The flames of war spread for five hundred miles, and Kingdom Z, having enjoyed peace for hundreds of years, could not withstand the army of Kingdom Y. Thus, people pinned all their hopes on the Knights, waiting for a true hero to be born and lead justice to defeat evil.

The Knights certainly have the ability to defeat the evil forces, but there are often conflicts among them. Each knight has exactly one knight they hate the most (which is not themselves), and they will absolutely refuse to go on an expedition with the person they hate the most.

As the war rages and the people suffer, it is urgent to organize a knight legion to join the battle! The King has given you a difficult task: select a knight legion from all the knights such that there are no conflicting pairs within the legion (i.e., there is no case where a knight and the person they hate the most are both selected), and maximize the total combat power of this legion.

To describe combat power, we number the knights from $1$ to $N$ and assign an estimated combat power to each knight. The combat power of a legion is the sum of the combat power of all its knights.

Input

The first line contains a positive integer $N$, describing the number of knights.

The next $N$ lines each contain two positive integers, describing the combat power of each knight and the knight they hate the most, in order.

Output

The output should contain a single integer, representing the combat power of the selected knight legion.

Examples

Input 1

3
10 2
20 3
30 1

Output 1

30

Constraints

For 30% of the test data, $N \le 10$.

For 60% of the test data, $N \le 100$.

For 80% of the test data, $N \le 10\,000$.

For 100% of the test data, $N \le 1\,000\,000$, and the combat power of each knight is a positive integer not exceeding $1\,000\,000$.