#1381. [USACO22OPEN] Visits S

[USACO22OPEN] Visits S

题目描述

Bessie 的 NN(2≤N≤1052\le N\le 10^5)个奶牛伙伴(编号为 1⋯N1\cdots N)每一个都拥有自己的农场。对于每个 1≤i≤N1\le i\le N,伙伴 ii 想要访问伙伴 aia_i(ai≠ia_i\neq i)。

给定 1…N1\ldots N 的一个排列 (p1,p2,…,pN)(p_1,p_2,\ldots, p_N),访问按以下方式发生。

对于 11 到 NN 的每一个 ii:

  • 如果伙伴 apia_{p_i} 已经离开了她的农场,则伙伴 pip_i 仍然留在她的农场。
  • 否则,伙伴 pip_i 离开她的农场去访问伙伴 apia_{p_i} 的农场。这次访问会产生快乐的哞叫 vpiv_{p_i} 次(0≤vpi≤1090\le v_{p_i}\le 10^9)。

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

输入格式

输入的第一行包含 NN。

对于每一个 1≤i≤N1\le i\le N,第 i+1i+1 行包含两个空格分隔的整数 aia_i 和 viv_i。

输出格式

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

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

样例

4
2 10
3 20
4 30
1 40
90

题目来源:洛谷 P8269