원섭시의 빚 정산

시간 제한1초메모리 제한128 MB

요약

각 시민이 정확히 한 명에게 빚을 진 함수형 그래프에서, 모든 빚이 연쇄적으로 상환되도록 시가 지급해야 할 최소 총액을 구하는 문제입니다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, DFS
정답자: 아직 제출이 없습니다

문제

원섭시에는 N명의 시민이 있다. 각 시민은 정확히 한 명의 다른 시민에게 돈을 빌렸다. 시민 i에 대해 A_i는 시민 i에게 돈을 빌려준 사람의 번호이고, B_i는 시민 i가 갚아야 하는 금액이다.

시는 모든 빚을 갚게 하고 싶지만, 현재 모든 시민은 돈을 하나도 가지고 있지 않다. 시는 일부 시민에게 돈을 줄 수 있다. 어떤 시민이 자신이 갚아야 할 금액 이상을 가지게 되면, 그 시민은 채권자에게 돈을 갚을 수 있다. 돈을 받은 채권자는 그 돈을 나중에 자신의 빚을 갚는 데 사용할 수 있다. 빚을 갚고 돈이 남으면 그 돈은 그 시민이 가진다.

모든 채무 관계가 주어졌을 때, 모든 빚을 결국 갚을 수 있도록 시가 시민들에게 주어야 하는 돈의 총합의 최솟값을 구하시오.

입력

첫째 줄에 시민의 수 N (2 <= N <= 200,000)이 주어진다. 시민의 번호는 1번부터 N번까지이다.

다음 N개의 줄 중 i번째 줄에는 두 정수 A_i와 B_i가 주어진다. A_i는 시민 i에게 돈을 빌려준 사람의 번호이고, B_i는 시민 i가 갚아야 하는 금액이다 (1 <= A_i <= N, A_i != i, 1 <= B_i <= 10,000).

출력

모든 시민의 빚을 해결하기 위해 필요한 돈의 총합의 최솟값을 출력한다.

예제3

예제 1
입력
```
4
2 100
1 100
4 70
3 70
```
예상 출력
```
170
```
예제 2
입력
```
3
2 120
3 50
2 80
```
예상 출력
```
150
```
예제 3
입력
```
5
3 30
3 20
4 100
5 40
3 60
```
예상 출력
```
110
```