电报

题目来源

JOISC 2016 Day 3

题目描述

给出 $N$ 个点，每个点的出度均为$1$，给出这 $N$ 个点初始指向的点 $A_i$ ，和改变这个点指向的目标所需要的价值 $C_i$。 求让所有点强连通的最小花费。

输入格式

第一行输入一个数 $N(1\leq N\leq 10^5)$ 表示点的个数。

之后的 $N$ 行每行两个数 $A_i, C_i(1\leq A_i\leq N, A_i\neq i, 1\leq C_i\leq 10^9)$。

输出格式

共一行，为让所有点强连通的最小花费。

样例输入

4
2 2
1 4
1 3
3 1

样例输出

4