Telegram

Problem Source

JOISC 2016 Day 3

Problem Description

There are $N$ points. Each point has out-degree exactly $1$. You are given, for each point, the point $A_i$ it initially points to, and the cost $C_i$ required to change where this point points.

Find the minimum total cost needed to make all points strongly connected.

Input Format

The first line contains one integer $N(1\leq N\leq 10^5)$, the number of points.

The following $N$ lines each contain two integers $A_i, C_i(1\leq A_i\leq N, A_i\neq i, 1\leq C_i\leq 10^9)$.

Output Format

Output one line: the minimum cost to make all points strongly connected.

Sample Input

4
2 2
1 4
1 3
3 1

Sample Output

4

Constraints

$1\leq N\leq 10^5$; $1\leq A_i\leq N$, $A_i\neq i$; $1\leq C_i\leq 10^9$.

Hint

• The given graph is a functional graph (every vertex has out-degree 1), so it consists of directed cycles with trees feeding into them. For the whole graph to be strongly connected, all $N$ vertices must lie on a single directed cycle; the answer is the minimum cost to reorient some edges so that this happens.