난국(Kriz)의 우두머리는 이 문제를 해결하려한다. 마을에서 소수의 사람에게 빚을 갚을 수 있게 돈을 줄 것이다. 몇몇 사람이 그들의 돈을 돌려받으면 연쇄반응이 시작될 거다.

- 예1 : A가 마을로부터 돈을 받는다. A는 돈을 B에게 빚을 갚는데 사용한다. B는 A에게 받은 돈을 C에게 빚을 갚는데 사용한다. (계속) 만약 B가 빚을 갚을 만큼 돈이 충분하지 않다면 채권자들은 갚을 수 있을 때까지 기다려준다. 만약 돈이 충분히 있다면 B는 갚고 난 뒤에 남은 돈을 계속 갖고 있는다.

- 예2 : 만약 난국(Kriz)에 두 사람이 살고 있다면 서로 100달러의 빚을 지고 있다, 마을은 그들 중 한명에게 100달러를 줄 것이고 그들은 서로에게 빚을 갚을 수 있다.

당신이 할 일은 마을 주민 중 일부에게 줄 수 있는 총 금액의 최소 금액을 계산한 후 위에서 설명한 돌려막기 프로토콜로 모든 채권자에게 돈을 갚습니다.

입력

• 첫 번째 줄에 1부터 N의 형태로 번호가 부여된 난국(Kriz)의 주민의 수 N(2<=N<=200,000)을 입력합니다.
• 첫 번째 줄 다음부터 N줄까지는 공간을 사이로 두개의 정수를 입력합니다.
• 각 i번째 줄의 첫 번째 수 Ai(1<=Ai<=N , Ai != i)는 돈을 빌린 사람을 의미하고 두 번째 수 Bi(1<=Bi<=10,000)는 빌린 돈의 양을 나타냅니다.

출력

입출력 예

입력

4
2 100
1 100
4 70
3 70

출력

170

입력

3
2 120
3 50
2 80

출력

150

입력

5
3 30
3 20
4 100
5 40
3 60

출력

110

출처:coci 2011
번역:iam6ear