题目描述

Bessie 的 $N$ 个奶牛伙伴（编号为$1 \dots N$）每一个都拥有自己的农场。

对于每个 $1≤i≤N$，伙伴 $i$ 想要访问伙伴 $a_i（a_i≠i）$。

给定 $1…N$ 的一个排列 $(p_1,p_2,\dots p_N)$，访问按以下方式发生。

对于 $1$ 到 $N$ 的每一个 $i$：

• 如果伙伴 $a_{pi}$ 已经离开了她的农场，则伙伴 $p_i$ 仍然留在她的农场。
• 否则，伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{pi}$ 的农场。这次访问会产生快乐的哞叫 $v_{pi}$ 次。

对于所有可能的排列 $p$，计算所有访问结束后可能得到的最大哞叫次数。

输入格式

输入的第一行包含 $N$。

对于每一个 $1≤i≤N$， 第 $i+1$ 行包含两个空格分隔的整数 $a_i$ 和 $v_i$。

输出格式

输出一个整数，为所求的答案。

4
2 10
3 20
4 30
1 40

90

提示

$2≤N≤10^5,$
$1≤a_i≤N$,
$0≤v_i≤10^9。$

样例解释

如果 $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$ 中访问结束后得到的最大可能的哞叫次数。