P3651 Time to Spread Wings (はばたきのとき)

**The ship sails on, let's set off toward the future.** **The ship sets sail, embarking on a journey toward the future.** **The blue sky is smiling (what do you want to do?).** **The azure sky is smiling (what do you want to do?).** **Let's become light; I want to illuminate the future.** **Become a ray of light; I want to shine on the future.** **Radiance overflows from the heart; I long to see the scenery even farther ahead.** **Brilliance wells up from the heart; I wish to behold the view farther ahead.** **Ah! Raise the future ticket we've finally gotten…!** **Ah! Wave the future ticket we've finally obtained…!**  We, Aqours, have finally begun to shine! February 25 and 26 will be the days we perform at Yokohama ARENA! And it will be broadcast in many theaters across all of Japan, and even around the world! It seems the broadcast is relayed via satellites! Mirai zura!

However, it seems there is some trouble with the relay satellites… We have a total of $N$ relay satellites, numbered $1$ to $N$. Each relay satellite can and only can receive data unidirectionally from exactly one other relay satellite. The $i$-th satellite is currently set to receive data from the $A_i$-th satellite (called the source). The source of these relay satellites can be modified, but each modification costs some money. It is said that to achieve relaying, these satellites must be able to communicate with each other pairwise (directly or indirectly). Although Mari is very rich, expenses this large still need to be planned in advance. So, can you help us calculate the minimum total amount of money needed?

The first line contains an integer $N$. Then $N$ lines follow. Each line contains $2$ integers $A_i, C_i$, indicating that initially the $i$-th relay satellite receives data from the $A_i$-th satellite, and the cost required to adjust the source of this satellite.

Output a single integer, which is the minimum cost that Mari needs to prepare.

### Constraints and Notes - For $10\%$ of the testdata, $N \le 10$. - For $40\%$ of the testdata, $N \le 15$. - For $70\%$ of the testdata, $N \le 3000$. - For $100\%$ of the testdata, $2 \le N \le 100000$, $1 \le C_i \le 10^9$. ### Easter egg In fact, LoveLive’s live satellite relay uses only one satellite, and it is never encrypted. As a result, as long as you have a satellite dish, you can secretly watch the live broadcast at home — the legendary satellite source. lin_toto: Bandai Namco even bought out Shallow Water Bay, yet there was only a replay, so I had to go to Hong Kong’s the sky to watch (wry smile). As for why watch a relay screening, eplus says for LoveLive series concerts, everyone can enter lotteries and try to buy; if you manage to buy a ticket, I lose. So last year during μ's Final LoveLive, lin_toto took down eplus with a botnet and then managed to buy tickets. This year, eplus didn’t even allow rush purchases; it was all lotteries. If you get selected, I lose. So lin_toto went to watch the relay screening. Translated by ChatGPT 5