暂无测试数据。

英文题面

Each of Bessie’s $N$ ($2\le N\le 10^5$) bovine buddies (conveniently labeled$1\ldots N$) owns her own farm. For each $1\le i\le N$, buddy $i$ wants to visit buddy $a_i$ ($a_i\neq i$).

Given a permutation $(p_1,p_2,\ldots, p_N)$ of $1\ldots N$, the visits occur as follows.For each $i$ from $1$ up to $N$:

If buddy $a_{p_i}$ has already departed her farm, then buddy $p_i$ remains at her own farm.Otherwise, buddy $p_i$ departs her farm to visit buddy $a_{p_i}$’s farm. This visit results in a joyful "moo" being uttered $v_{p_i}$ times ($0\le v_{p_i}\le 10^9$).

Compute the maximum possible number of moos after all visits, over all possible permutations $p$.

译文

给定 $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$，计算所有访问结束后可能得到的最大哞叫次数。

输入格式

The first line contains $N$.

For each $1\le i\le N$, the $i+1$-st line contains two space-separated integers$a_i$ and $v_i$.

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

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

输出格式

A single integer denoting the answer.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

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

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

数据范围

• Test cases 2-3 satisfy $a_i\neq a_j$ for all $i\neq j$.
• Test cases 4-7 satisfy $N\le 10^3$.
• Test cases 8-11 satisfy no additional constraints.

测试点 2-3 对于所有的 $i\neq j$ 满足 $a_i\neq a_j$。测试点 4-7 满足 $N\le 10^3$。测试点 8-11 没有额外限制。

4
2 10
3 20
4 30
1 40

90