P6486 [COCI 2010/2011 #4] DUGOVI

In a small town, there are $n$ residents. Each resident has borrowed some money from **exactly one other** resident. Now it is time to repay the debts. But the problem is that everyone has spent all their money; that is, nobody is able to repay their debt. This leads to many conflicts. The mayor decides to solve this problem. He plans to give some money to a part of the residents so that they can use it to repay their debts. However, once some residents receive money, a chain reaction begins. For example, $A$ receives money from the mayor. $A$ quickly uses this money to repay the debt to $B$. Then $B$ repays the debt to $C$, and so on. Here, if $B$ does not have enough money to pay off the debt at once, then he will keep the money temporarily until he has enough; if there is money left after repaying the debt, $B$ will also keep it. (The behavior of $B$ applies to any person.) Another example: if two residents in the town **owe each other** $100$ dollars, then the mayor only needs to give $100$ dollars to one of them, and both debts will be settled. You need to write a program to compute: what is the minimum amount of money the mayor must pay to some residents to settle all debts?

The first line contains an integer $n$, the number of residents in the town. The next $n$ lines each contain two integers $A_i, B_i$, meaning that person $i$ owes person $A_i$ $B_i$ dollars. Residents are numbered from $1$ to $n$.

Output one line with one integer, the minimum amount the mayor must pay.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $2\le n\le 2\times 10^5$, $1\le A_i\le n$ and $A_i\neq i$, $1\le B_i\le 10^4$. #### Notes **Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T5 DUGOVI***。 Translated by ChatGPT 5