베시의 소 친구 \(N\)마리는 각각 자신의 농장을 가지고 있다. 소 친구들은 편의상 \(1\)번부터 \(N\)번까지 번호가 붙어 있다. 각 \(1\le i\le N\)에 대해, \(i\)번 친구는 \(a_i\)번 친구를 방문하고 싶어 한다. (\(a_i\ne i\))

\(1,2,\ldots,N\)의 순열 \((p_1,p_2,\ldots,p_N)\)이 주어졌다고 하자. 방문은 다음과 같이 이루어진다.

\(i=1\)부터 \(N\)까지 차례대로 다음 과정을 수행한다.

• \(a_{p_i}\)번 친구가 이미 자신의 농장을 떠났다면, \(p_i\)번 친구는 자신의 농장에 남는다.
• 그렇지 않다면, \(p_i\)번 친구는 자신의 농장을 떠나 \(a_{p_i}\)번 친구의 농장을 방문한다. 이 방문으로 즐거운 음매 소리가 \(v_{p_i}\)번 울린다.

가능한 모든 순열 \(p\) 중에서, 모든 방문이 끝난 뒤 울린 음매 소리 횟수의 최댓값을 구하여라.

입력

첫째 줄에 소 친구의 수 \(N\)이 주어진다. (\(2\le N\le 10^5\))

다음 \(N\)개의 줄 중 \(i\)번째 줄에는 두 정수 \(a_i\)와 \(v_i\)가 공백으로 구분되어 주어진다. (\(a_i\ne i\), \(0\le v_i\le 10^9\))

출력

가능한 음매 소리 횟수의 최댓값을 출력한다.

답의 크기가 클 수 있으므로 C/C++에서는 long long과 같은 64비트 정수 자료형을 사용해야 할 수 있다.

예제 입력

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\)번, \(4\)번 친구가 차례로 방문하여 각각 \(20\), \(30\), \(40\)번의 음매 소리를 낸다. 마지막으로 \(1\)번 친구는 \(2\)번 친구가 이미 떠난 것을 보고 아무 일도 하지 않는다. 따라서 음매 소리는 총 \(20+30+40=90\)번 울리며, 이것이 가능한 최댓값이다.

서브태스크

출처

USACO 2022 US Open Contest, Silver, Problem 1. Visits