问题描述

Bessie 的 N（ 2≤N≤10^5 ）个奶牛伙伴（编号为 1…N）每一个都拥有自己的农场。对于每个 1≤i≤N，伙伴 i 想要访问伙伴 ai（ai≠i）。

给定 1…N 的一个排列 (p1,p2,…,pN)，访问按以下方式发生。

对于 1 到 N 的每一个 i：

如果伙伴 api 已经离开了她的农场，则伙伴 pi 仍然留在她的农场。

否则，伙伴 pi 离开她的农场去访问伙伴 api 的农场。这次访问会产生快乐的哞叫 vpi 次（0≤vpi≤10^9）。

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

输入格式

输入的第一行包含 N。

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

输出格式

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

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。

输入样例：

4
2 10
3 20
4 30
1 40

输出样例：

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

测试点性质：

测试点 2-3 对于所有的 i≠j 满足 ai≠aj。

测试点 4-7 满足 N≤103。

测试点 8-11 没有额外限制。

供题：Benjamin Qi，Michael Cao