Knights

Problem Source

ZJOI 2008

Problem Description

The Knight Order of country Z is a powerful and influential organization, gathering elites from all over the land. They rob the rich to help the poor, punish evil and promote good, and are praised by all walks of society.

Recently, something terrible happened: the evil country Y launched a war of aggression against Z. The flames of war stretched for five hundred li, and how could a country that had lived in peace for centuries withstand Y's army? So the people pinned all their hopes on the Knight Order, like waiting for a true Son of Heaven to be born, to lead justice to defeat evil.

The Knight Order certainly has the ability to defeat the evil forces, but the knights often have conflicts among themselves. Each knight has exactly one other knight he hates the most (of course, not himself), and he will absolutely never march to battle together with the one he hates most.

With the war raging and the people suffering, organizing a knight legion to join the fight is urgent! The king has given you a difficult task: select a knight legion from all the knights such that no two members of the legion hate each other (there must be no case where a knight is selected together with the one he hates most), and such that this legion is as combat-ready as possible.

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

Input Format

The first line contains one integer $n(1\leq n\leq 10^6)$, the number of knights in the order.

The following $n$ lines each contain two integers, describing in order each knight's combat power and the knight he hates the most. Each knight's combat power is a positive integer not exceeding $10^6$.

Output Format

Output one line containing a single integer: the combat power of the knight legion you selected.

Sample Input

3
10 2
20 3
30 1

Sample Output

30

Constraints

$1\leq n\leq 10^6$; each knight's combat power is a positive integer not exceeding $10^6$.

Hint

• The "hates" relation is a functional graph (every knight points to exactly one other knight), so the whole structure decomposes into a forest of "base-ring trees" (a tree attached to a single cycle). The classic approach is to cut each cycle open and run a tree DP for both choices of the two cycle endpoints, then combine the two results.