Problem Description

In a small town, there are $n$ residents, each of whom has borrowed some money from exactly one other resident.

It's time to repay the debts, but the problem is that everyone has spent all their money; in other words, no one is capable of repaying their debts. This has led to many conflicts.

The mayor has decided to address this issue. He plans to give some money to a portion of the residents so they can use it to repay their debts. However, once some residents receive the money, a series of chain reactions begins.

For example, if $A$ receives money from the mayor, $A$ will immediately use it to repay $B$'s debt. $B$ will then repay $C$'s debt, and so on.

If $B$ does not have enough money to repay in one go, $B$ will keep the money until it is sufficient; if there is any remaining after repaying the debt, $B$ will keep it. (This behavior applies to any individual.)

Another example: If two residents in the town owe each other $100, the mayor only needs to give $100 to one of them, and both debts will be resolved.

You need to write a program to calculate the minimum amount of money the mayor needs to spend to settle all debts.

Input Format

The first line contains an integer $n$, representing the number of residents in the town.

The next $n$ lines each contain two integers $A_i$ and $B_i$, indicating that the $i$-th person owes the $A_i$-th person $B_i$ dollars.

Residents are numbered from $1$ to $n$.

Output Format

Output a single integer, representing the minimum amount of money the mayor needs to spend.

Sample Input and Output

Sample Input #1

4
2 100
1 100
4 70
3 70

Sample Output #1

170

Sample Input #2

3
2 120
3 50
2 80

Sample Output #2

150

Sample Input #3

5
3 30
3 20
4 100
5 40
3 60

Sample Output #3

110

Notes

Data Size and Constraints

For $100\%$ of the data, 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.

见题面 Input 部分

见题面 Output 部分