방문

Bessie의 소 $N$마리($2\le N\le 10^5$)에게는 $1\ldots N$번의 번호가 붙어 있고, 각자 자기 농장을 가지고 있다. 각 $1\le i\le N$에 대해 소 $i$는 소 $a_i$를 방문하려 한다($a_i\neq i$).

$1\ldots N$의 순열 $(p_1,p_2,\ldots,p_N)$이 주어지면 방문은 다음과 같이 진행된다.

$i$를 $1$부터 $N$까지 차례로 본다.

• 소 $a_{p_i}$가 이미 농장을 떠났다면 소 $p_i$는 자기 농장에 남는다.
• 그렇지 않다면 소 $p_i$는 농장을 떠나 소 $a_{p_i}$의 농장을 방문한다. 이 방문으로 기쁜 울음소리 "moo"가 $v_{p_i}$번 울린다($0\le v_{p_i}\le 10^9$).

모든 방문이 끝난 뒤 울린 "moo"의 최대 개수를 구하라. 가능한 모든 순열 $p$에 대한 최댓값이다.

첫 줄에 $N$이 주어진다.

각 $1\le i\le N$에 대해 $(i+1)$번째 줄에 공백으로 구분된 정수 $a_i$와 $v_i$가 주어진다.

답을 나타내는 정수 하나를 출력한다.

값이 커질 수 있으므로 64비트 정수형(C/C++의 "long long" 등)이 필요할 수 있다.

$p=(1,4,3,2)$이면 다음과 같다.

• 소 $1$이 소 $2$의 농장을 방문해 "moo"가 $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$에 대한 최댓값이다.