Description

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?

Input Format

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 Format

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

4
2 2
1 6
1 3
3 1

5

Hint

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