시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 0 0 0.000%

문제

원섭시에는 N명의 시민들이 살고 있다. 이 마을에 살고있는 모든 시민은 각각 다른 시민 1명에게 돈을 빌렸다. 이제 모든 빚을 갚아야하는 시간이다. 그런데, 큰 문제가 생겨서 모든 사람들이 돈을 갚을 수 없게 되었다. 그 이유는 각자 가지고 있는 돈을 모두 써버렸기 때문이다.

원섭시의 시장 고원섭은 이런 악순환을 해결하고자 마을에서 일부 사람들에게 돈을 주기로 했다. 이렇게 일부 사람들이 돈을 받게 되면, 그 돈으로 돈을 갚고, 또 받은 사람은 돈을 갚을 수 있게 된다. 예를 들어, A가 마을에서 돈을 받았다고 하자. 그럼 A는 B에게 돈을 갚을 수 있고, B는 C에게 돈을 갚을 수 있다. 만약, B가 빚을 갚을 수 있는 충분한 돈이 없다면, 충분한 돈이 생길 때 까지 기다리면 된다. 또, B가 돈을 더 가지고 있다면, B는 그 돈을 가지면 된다.

다른 예로, 이 마을에 두 사람이 살고 있고, 두 사람이 서로에게 100원을 빌린 경우를 생각해보자. 이 경우에 마을에서 두 사람 중 한 사람에게 100원을 주면, 서로 빚을 갚을 수 있게 된다.

원섭시의 모든 시민들의 채무 관계가 주어졌을 때, 마을의 악순환을 해결하기 위해 필요한 금액의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시민의 수 N (2 ≤ N ≤ 200,000)이 주어진다. 각 사람의 번호는 1번부터 N번이다.

다음 N개의 줄에는 공백으로 구분되어져 있는 두 정수 Ai와 Bi가 주어진다. Ai는 i번 사람이 돈을 빌린 사람의 번호이고, Bi는 갚아야 하는 금액이다. (1 ≤ Ai ≤ N, Ai ≠ i, 1 ≤ Bi ≤ 10,000)

출력

첫째 줄에 시민들의 빚을 해결하기 위해 필요한 최소 금액을 출력한다.

예제 입력

4
2 100
1 100
4 70
3 70

예제 출력

170

힌트