JOI 群岛是一个漂浮在太平洋上的小岛国。JOI 群岛共有 $N$ 个岛屿，编号从 $1$ 到 $N$。

JOI 群岛岛屿间的通信主要通过无线电进行。每个岛上各有一个无线电发射机和一个接收机。发射机可以向全方向发送电波，但接收机只能接收来自特定方向的电波。因此，每个接收机一次只能接收来自某一个特定岛屿的电波。不过，通过改变接收机的朝向，可以改变其能够接收电波的来源岛屿。

目前，岛屿 $i$ ($1 \le i \le N$) 的接收机可以接收来自岛屿 $A_i$ ($A_i \neq i$) 的电波。此外，改变岛屿 $i$ 的接收机朝向所需的成本为 $C_i$，无论将其朝向改为接收哪个岛屿的电波，成本均相同。

JOI 群岛作为公共事业提供电报服务。当岛屿 $j$ ($1 \le j \le N, j \neq i$) 的接收机能够接收来自岛屿 $i$ ($1 \le i \le N$) 的电波时，就可以通过无线通信从岛屿 $i$ 向岛屿 $j$ 发送电报。此外，电报也可以经由若干个岛屿中转发送。也就是说，对于岛屿 $i, j, k$ ($1 \le i, j, k \le N$ 且 $i, j, k$ 互不相同)，如果可以从岛屿 $i$ 向岛屿 $j$ 发送电报，且可以从岛屿 $j$ 向岛屿 $k$ 发送电报，那么就可以从岛屿 $i$ 向岛屿 $k$ 发送电报。无法通过无线通信以外的方法发送电报。

作为 JOI 群岛的通信大臣，你希望实现从任意岛屿向任意岛屿发送电报。为此，可能需要改变某些岛屿接收机的朝向。改变若干个岛屿接收机朝向的总成本，即为改变各个接收机朝向所需成本之和。

请计算实现从任意岛屿向任意岛屿发送电报所需的最小成本。

输入格式

从标准输入读取以下数据：

• 第 $1$ 行包含一个整数 $N$，表示 JOI 群岛共有 $N$ 个岛屿。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含以空格分隔的两个整数 $A_i$ 和 $C_i$，表示岛屿 $i$ 的接收机目前可以接收来自岛屿 $A_i$ 的电波，且改变其朝向的成本为 $C_i$。

输出格式

将实现从任意岛屿向任意岛屿发送电报所需的最小成本输出到标准输出，占一行。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 100\,000$
• $1 \le A_i \le N$ ($1 \le i \le N$)
• $A_i \neq i$ ($1 \le i \le N$)
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$)

子任务

• 子任务 1 [10 分]：满足 $N \le 10$。
• 子任务 2 [30 分]：满足 $N \le 15$。
• 子任务 3 [30 分]：满足 $N \le 3\,000$。
• 子任务 4 [30 分]：无附加限制。

样例

样例输入 1

4
2 2
1 4
1 3
3 1

样例输出 1

4

样例输入 2

4
2 2
1 6
1 3
3 1

样例输出 2

5

样例输入 3

4
2 2
1 3
4 2
3 3

样例输出 3

4

样例输入 4

3
2 1
3 1
1 1

样例输出 4

0