Bessie 的 NN
（2≤N≤1052≤N≤105
）个奶牛伙伴（编号为 1…N1…N
）每一个都拥有自己的农场。对于每个 1≤i≤N1≤i≤N
，伙伴 ii
想要访问伙伴 aiai
（ai≠iai≠i
）。
给定 1…N1…N 的一个排列 (p1,p2,…,pN)(p1,p2,…,pN)，访问按以下方式发生。
对于 11 到 NN 的每一个 ii：
-
如果伙伴 apiapi 已经离开了她的农场，则伙伴 pipi 仍然留在她的农场。
-
否则，伙伴 pipi 离开她的农场去访问伙伴 apiapi 的农场。这次访问会产生快乐的哞叫 vpivpi 次（0≤vpi≤1090≤vpi≤109）。
对于所有可能的排列 pp，计算所有访问结束后可能得到的最大哞叫次数。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含 NN。
对于每一个 1≤i≤N1≤i≤N，第 i+1i+1 行包含两个空格分隔的整数 aiai 和 vivi。
输出格式（输出至终端 / 标准输出）：
输出一个整数，为所求的答案。 注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。
输入样例：
4
2 10
3 20
4 30
1 40
输出样例：
90
如果 p=(1,4,3,2)p=(1,4,3,2)，则
-
伙伴 11 访问伙伴 22 的农场，产生 1010 次哞叫。
-
伙伴 44 看到伙伴 11 已经离开了农场，所以无事发生。
-
伙伴 33 访问伙伴 44 的农场，又产生 3030 次哞叫。
-
伙伴 22 看到伙伴 33 已经离开了农场，所以无事发生。
这样总计得到了 10+30=4010+30=40 次哞叫。
另一方面，如果 p=(2,3,4,1)p=(2,3,4,1)，则
-
伙伴 22 访问伙伴 33 的农场，产生 2020 次哞叫。
-
伙伴 33 访问伙伴 44 的农场，产生 3030 次哞叫。
-
伙伴 44 访问伙伴 11 的农场，产生 4040 次哞叫。
-
伙伴 11 看到伙伴 22 已经离开了农场，所以无事发生。
这样总计得到了 20+30+40=9020+30+40=90 次哞叫。可以证明这是所有可能的排列 pp 中访问结束后得到的最大可能的哞叫次数。
测试点性质：
-
测试点 2-3 对于所有的 i≠ji≠j 满足 ai≠ajai≠aj。
-
测试点 4-7 满足 N≤103N≤103。
-
测试点 8-11 没有额外限制。
供题：Benjamin Qi，Michael Cao