Visits

문제

Each of Bessie’s $NN$ ($2\le N\le {10}^{5}2\backslash le\; N\backslash le\; 10^5$) bovine buddies (conveniently labeled $1\dots N1\backslash ldots\; N$) owns her own farm. For each $1\le i\le N1\backslash le\; i\backslash le\; N$, buddy $ii$ wants to visit buddy $a_{i}a\_i$ ($a_i\mathrm{\ne }ia\_i\backslash neq\; i$).

Given a permutation $(p_1,p_2,\dots ,p_N)(p\_1,p\_2,\backslash ldots,\; p\_N)$ of $1\dots N1\backslash ldots\; N$, the visits occur as follows.

For each $ii$ from $11$ up to $NN$:

• If buddy $a_{p_i}a\_\{p\_i\}$ has already departed her farm, then buddy $p_{i}p\_i$ remains at her own farm.
• Otherwise, buddy $p_{i}p\_i$ departs her farm to visit buddy $a_{p_i}a\_\{p\_i\}$’s farm. This visit results in a joyful "moo" being uttered $v_{p_i}v\_\{p\_i\}$ times ($0\le v_{p_i}\le {10}^{9}0\backslash le\; v\_\{p\_i\}\backslash le\; 10^9$).

Compute the maximum possible number of moos after all visits, over all possible permutations $pp$.

입력

The first line contains $NN$.

For each $1\le i\le N1\backslash le\; i\backslash le\; N$, the $i+1i+1$-st line contains two space-separated integers $a_{i}a\_i$ and $v_{i}v\_i$.

출력

A single integer denoting the answer.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

힌트

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

• Buddy $11$ visits buddy $22$'s farm, resulting in $1010$ moos.
• Buddy $44$ sees that buddy $11$ has already departed, so nothing happens.
• Buddy $33$ visits buddy $44$'s farm, adding $3030$ moos.
• Buddy $22$ sees that buddy $33$ has already departed, so nothing happens.

This gives a total of $10+30=4010+30=40$ moos.

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

• Buddy $22$ visits buddy $33$'s farm, causing $2020$ moos.
• Buddy $33$ visits buddy $44$'s farm, causing $3030$ moos.
• Buddy $44$ visits buddy $11$'s farm, causing $4040$ moos.
• Buddy $11$ sees that buddy $22$ has already departed, so nothing happens.

This gives $20+30+40=9020+30+40=90$ total moos. It can be shown that this is the maximum possible amount after all visits, over all permutations $pp$.

4
2 10
3 20
4 30
1 40

90