Problem Description

Bessie has $N$ ($2\le N\le 10^5$) cow friends (numbered $1\cdots N$), and each of them owns her own farm. For each $1\le i\le N$, friend $i$ wants to visit friend $a_i$ ($a_i\neq i$).

Given a permutation $(p_1,p_2,\ldots, p_N)$ of $1\ldots N$, the visits happen as follows.

For each $i$ from $1$ to $N$:

• If friend $a_{p_i}$ has already left her farm, then friend $p_i$ stays at her farm.
• Otherwise, friend $p_i$ leaves her farm to visit friend $a_{p_i}$'s farm. This visit produces happy moos $v_{p_i}$ times ($0\le v_{p_i}\le 10^9$).

Among all possible permutations $p$, compute the maximum total number of moos that can be obtained after all visits finish.

Input Format

The first line contains $N$.

For each $1\le i\le N$, line $i+1$ contains two space-separated integers $a_i$ and $v_i$.

Output Format

Output one integer, the required answer.

Note that the integers in this problem may require 64-bit integer types (for example, "long long" in C/C++).

4
2 10
3 20
4 30
1 40

90

Hint

[Sample Explanation]

If $p=(1,4,3,2)$, then:

• Friend $1$ visits friend $2$'s farm, producing $10$ moos.
• Friend $4$ sees that friend $1$ has already left her farm, so nothing happens.
• Friend $3$ visits friend $4$'s farm, producing another $30$ moos.
• Friend $2$ sees that friend $3$ has already left her farm, so nothing happens.

So in total we get $10+30=40$ moos.

On the other hand, if $p=(2,3,4,1)$, then:

• Friend $2$ visits friend $3$'s farm, producing $20$ moos.
• Friend $3$ visits friend $4$'s farm, producing $30$ moos.
• Friend $4$ visits friend $1$'s farm, producing $40$ moos.
• Friend $1$ sees that friend $2$ has already left her farm, so nothing happens.

So in total we get $20+30+40=90$ moos. It can be proven that this is the maximum possible number of moos after all visits finish among all possible permutations $p$.

Translated by ChatGPT 5