You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一张 $n$ 个点的有向图，每个点都有且仅有一条出边，初始时 $i$ 号点的出边连向 $a_i$ 号点。

你每次可以选择一个点 $i$，改变它的出边所连向的点，并花费 $c_i$ 的代价。求使得这张图强连通的最小总代价。

输入格式

从文件 $story.in$ 中读入数据。

第一行一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行两个正整数 $a_i,c_i$。

输出格式

输出到文件 $story.out$ 中。

一行一个整数表示最小总代价。

样例 1 输入

4
2 2
1 4
1 3
3 1

样例 1 输出

4

样例 1 解释

将 $2$ 号点的出边改为连向节点 $4$，花费的代价为 $c_2=4$。

样例 2 输入

4
2 2
1 6
1 3
3 1

样例 2 输出

5

样例 3

见右侧文件下的 $story3.in$ 与 $story3.ans$。

样例 4

见右侧文件下的 $story4.in$ 与 $story4.ans$。

数据范围与提示

对于所有测试数据，保证 $2≤n≤10^5，1≤a_i≤n，a_i≠i，1≤c_i≤10^9$。

本题采用子任务捆绑测试。每个子任务的具体限制见下表：