[USACO22OPEN] Visits S

题目描述

Bessie 的 $N$($2\le N\le 10^5$)个奶牛伙伴(编号为 $1\cdots N$)每一个都拥有自己的农场。对于每个 $1\le i\le N$,伙伴 i 想要访问伙伴 $a_i$($a_i\neq i$)。 给定 $1\ldots N$ 的一个排列 $(p_1,p_2,\ldots, p_N)$,访问按以下方式发生。 对于 $1$ 到 $N$ 的每一个 $i$: - 如果伙伴 $a_{p_i}$ 已经离开了她的农场,则伙伴 $p_i$ 仍然留在她的农场。 - 否则,伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{p_i}$ 的农场。这次访问会产生快乐的哞叫 $v_{p_i}$ 次($0\le v_{p_i}\le 10^9$)。 对于所有可能的排列 $p$,计算所有访问结束后可能得到的最大哞叫次数。

输入输出格式

输入格式


输入的第一行包含 $N$。 对于每一个 $1\le i\le N$,第 $i+1$ 行包含两个空格分隔的整数 $a_i$ 和 $v_i$。

输出格式


输出一个整数,为所求的答案。 **注意这个问题涉及到的整数可能需要使用 64 位整数型(例如,C/C++ 中的 "long long")。**

输入输出样例

输入样例 #1

4
2 10
3 20
4 30
1 40

输出样例 #1

90

说明

【样例解释】 如果 $p=(1,4,3,2)$,则 - 伙伴 $1$ 访问伙伴 $2$ 的农场,产生 $10$ 次哞叫。 - 伙伴 $4$ 看到伙伴 $1$ 已经离开了农场,所以无事发生。 - 伙伴 $3$ 访问伙伴 $4$ 的农场,又产生 $30$ 次哞叫。 - 伙伴 $2$ 看到伙伴 $3$ 已经离开了农场,所以无事发生。 这样总计得到了 $10+30=40$ 次哞叫。 另一方面,如果 $p=(2,3,4,1)$,则 - 伙伴 $2$ 访问伙伴 $3$ 的农场,产生 $20$ 次哞叫。 - 伙伴 $3$ 访问伙伴 $4$ 的农场,产生 $30$ 次哞叫。 - 伙伴 $4$ 访问伙伴 $1$ 的农场,产生 $40$ 次哞叫。 - 伙伴 $1$ 看到伙伴 $2$ 已经离开了农场,所以无事发生。 这样总计得到了 $20+30+40=90$ 次哞叫。可以证明这是所有可能的排列 $p$ 中访问结束后得到的最大可能的哞叫次数。