Description

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?

Input Format

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 Format

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

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

Hint

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 CONTEST #4 T5 DUGOVI。

Translated by ChatGPT 5